Dlaczego większe rozmiary wejściowe oznaczają trudniejsze instancje?

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ą?

complexity-theory time-complexity intuition

— Kaveh
źródło

„Bezpośrednio proporcjonalny” ma określone znaczenie matematyczne, które oznacza zasadniczo czas liniowy. Innymi słowy, jeśli dane wejściowe mają rozmiar , jeśli czas jest wprost proporcjonalny, algorytm działa w czasie . Wyobrażam sobie, że nie to masz na myśli, ponieważ wiele algorytmów nie działa w czasie liniowym, tzn. Podczas sortowania. Czy możesz wyjaśnić dalej?

n

$n$

c n

$cn$

— SamM

Pytasz więc o algorytm działający w czasie ? oznacza, że algorytm działa w tym samym czasie, niezależnie od wielkości wejścia, oznacza, że działa szybciej, gdy dane wejściowe stają się większe. Nie mogę wymyślić takiego, który działa w tym czasie poza górą mojej głowy, ale notacja jest dość powszechna, ponieważ algorytm często działa w czasie takim jak - w innym słowami, zajmuje to czas i istnieją inne terminy, które zmniejszają się wraz ze wzrostem wielkości wejściowej.

o (1)

$o(1)$

O (1)

$O(1)$

o (1)

$o(1)$

O (n^{2}) + o (1)

$O(n^2) + o(1)$

O (n^{2})

$O(n^2)$

— SamM

Dobre pytanie. A co z przeciw-przykładem obliczania czynników pierwszych dla jakiegoś dużego (jest to tylko rosnąca funkcja dla )? @Sam Zauważ, że funkcja rosnąca mówi, że czas musi maleć w pewnym punkcie wzdłuż linii rzeczywistej (tj. ).

c / n

$c / n$

c

$c$

n \geq c

$n \geq c$

f (b) < f (a), a < b

$f(b) < f(a), a < b$

— Casey Kuball,

@Darthfett Obawiam się, że nie podążam. Nie wszystkie rosnące funkcje maleją w pewnym momencie wzdłuż rzeczywistej linii.

— SamM

@Jennifer Tak, rozumiem, to ma sens. Polecam użycie terminu ponieważ ma on znaczenie, którego szukasz. Chciałbym jeszcze raz podkreślić, że bezpośrednia proporcjonalność oznacza liniowość; Rozumiem, o co ci chodzi, ale może być mylące dla tych, którzy czytają pytanie po raz pierwszy.

o (1)

$o(1)$

— SamM

Odpowiedzi:

Czy jest tak, że złożoność czasu jest zawsze rosnącą funkcją wielkości wejściowej? Jeśli tak, to dlaczego tak jest?

Nie. Rozważ maszynę Turinga, która zatrzymuje się po krokach, gdy wielkość wejściowa jest parzysta, i zatrzymuje się po krokach, gdy jest nieparzysty. $n$ $n$ $n^2$ $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.

— JeffE
źródło

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ą?

Niech oznacza rozmiar wejściowy. Aby odczytać cały wkład, maszyna Turinga potrzebuje już kroków. Więc jeśli założymy, że algorytm musi odczytać całe dane wejściowe (lub dla pewnej stałej ), zawsze skończy się przynajmniej liniowy czas działania. $n$ $n$ $n/c$ $c$

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 , 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 .

— Krzysztof
źródło

Istnieją algorytmy podliniowe. Na przykład zobacz people.csail.mit.edu/ronitt/sublinear.html . To dość nowa dziedzina, ale bardzo interesująca. Są na to inne kontrprzykłady. Znalezienie elementu z posortowaną listą zajmuje

w modelu RAM. Zgadzam się z ideą twojego postu. Nie ma sensu mieć algorytmu zajmującego mniej czasu, ponieważ dane wejściowe stają się większe, ponieważ nie ma czasu na odczytanie wszystkich danych wejściowych (skąd wiadomo, że zajmuje to mniej czasu?). Ale nie wiem, jak udowodnić, że nie istnieje, i że sztuczka nie mógł zrobić to

O (\log n)

$O(\log n)$

o (1)

$o(1)$

— SamM

@Sam: Przepraszam, nie widziałem twojego komentarza przed moją edycją (dodawanie algorytmów podliniowych).

— Christopher

wręcz przeciwnie; Nie widziałem Twojej edycji przed dodaniem mojego komentarza. Chciałbym go usunąć, ale druga połowa nadal obowiązuje, a dodatkowy link nie może zaszkodzić OP

— SamM

kontrprzykład: stała funkcja taka jak

. To, co opisujesz, działa dla funkcji, które muszą odczytać ich dane wejściowe.

f (x) = 0

$f(x)=0$

— Kaveh

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 , to znaczy wszystkie funkcje środowiska wykonawczego (w granicach) nie maleją. $(\mathbb{N},\leq)$ $\Omega(1)$

To powiedziawszy, średnie czasy działania mogą zawierać oscylujące elementy, na przykład Mergesort .

— Raphael
źródło

Nie widzę związku tej odpowiedzi z pytaniem.

— A.Schulz

@ A. Schulz Daje dowód na zasadnicze pytanie: „Czy to nie jest tak, że złożoność czasu jest zawsze rosnącą funkcją wielkości wejściowej?”, Czytając „rosnący” jako „nie malejący”, tzn. Niekoniecznie ściśle rosnący.

— Raphael

\neq

$\not=$

@ A. Schulz: Mimo to moja interpretacja wydaje się być tym, czym interesuje się Jennifer .

— Raphael