Poniżej załóżmy, że pracujemy z maszyną Turinga z nieskończoną taśmą.
Wyjaśniając komuś pojęcie złożoności czasowej i dlaczego mierzy się ją względem wielkości wejściowej instancji, natknąłem się na następujące twierdzenie:
[..] Na przykład naturalne jest, że potrzeba więcej kroków, aby pomnożyć dwie liczby całkowite przez 100 000 bitów, niż, powiedzmy, pomnożenie dwóch liczb całkowitych przez 3 bity.
Twierdzenie jest przekonujące, ale w jakiś sposób wymachuje ręką. We wszystkich algorytmach, które napotkałem, im większy rozmiar wejściowy, tym więcej kroków potrzebujesz. Mówiąc dokładniej, złożoność czasu jest monotonicznie rosnącą funkcją wielkości wejściowej.
Czy jest tak, że złożoność czasu jest zawsze rosnącą funkcją wielkości wejściowej? Jeśli tak, to dlaczego tak jest? Czy jest na to dowód poza wymachiwaniem ręką?
Odpowiedzi:
Nie. Rozważ maszynę Turinga, która zatrzymuje się po krokach, gdy wielkość wejściowa n jest parzysta, i zatrzymuje się po n 2 krokach, gdy n jest nieparzysty.n n n2) n
Jeśli masz na myśli złożoność problemu , odpowiedź brzmi: nie. Złożoność testowania pierwotności jest znacznie mniejsza dla liczb parzystych niż dla liczb nieparzystych.
źródło
Niech oznacza rozmiar wejściowy. Aby odczytać cały wkład, maszyna Turinga potrzebuje już n kroków. Więc jeśli założymy, że algorytm musi odczytać całe dane wejściowe (lub n / c dla pewnej stałej c ), zawsze skończy się przynajmniej liniowy czas działania.n n n / c do
Problem z definiowaniem algorytmów z „monotonicznie malejącą funkcją czasu działania” polega na tym, że trzeba jakoś zdefiniować czas działania dla . Musisz ustawić na skończoną wartość. Ale istnieją nieskończone możliwe wartości dla n > 1 , więc otrzymujesz funkcję, która jest stała dla nieskończonej wielu wartości.n = 1 n > 1
Prawdopodobnie interesujące są algorytmy podliniowe , które nie odczytują całego wejścia. Zobacz na przykład http://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Sublinear-time-Survey-BEATCS.pdf .
źródło
Zależność jest dobrze uzasadniona , tzn. Nie ma nieskończonych sekwencji spadających w liczbach naturalnych. Ponieważ (w najgorszym przypadku) funkcje środowiska wykonawczego są odwzorowane na wartości naturalne, dlatego wszystkie funkcje środowiska wykonawczego muszą być w Ω ( 1 ) , to znaczy wszystkie funkcje środowiska wykonawczego (w granicach) nie maleją.( N , ≤ ) Ω ( 1 )
To powiedziawszy, średnie czasy działania mogą zawierać oscylujące elementy, na przykład Mergesort .
źródło