Złożoność czasowa 2 ^ sqrt (n)

11

Rozwiązuję pytanie dotyczące algorytmu i moja analiza polega na tym, że będzie on działał na O (2 ^ sqrt (n)). Jak duże to jest? Czy to odpowiada O (2 ^ n)? Czy nadal jest to czas niepomiarowy?

Gaara
źródło
3
Proszę skomentować przyczynę głosowania w dół na pytanie. Dzięki!
Gaara,
4
Szczerze mówiąc, podejrzewam, że ludzie mylą to z niezwykle trywialnym pytaniem, ale nie jest od razu oczywiste, jak to udowodnić, więc pójdę napisać odpowiedź i zobaczę, czy to zmieni ludzkie zdanie.
Ixrec,
3
Pod-czas wykładniczy, druga definicja, według Wikipedii :; (Zastrzeżenie ja nie downvote i nie wiem wystarczająco dużo na ten temat powiedzieć, czy jest to poprawne, czy nie.)
rwong
1
Świetny! Czas podwykładniczy: „czas działania niektórych algorytmów może rosnąć szybciej niż jakikolwiek wielomian, ale nadal jest znacznie mniejszy niż wykładniczy”. To zdecydowanie odpowiada na moje pytanie i poszerza moją wiedzę na temat analizy Big O. Wielkie dzięki
Gaara,
1
Jest to znacznie mniej niż O (2 ^ n), szczególnie w przypadku dużych liczb. Weźmy przykład posiadania kolekcji 10 000 elementów. 2 ^ 10000 to liczba składająca się z około 3000 cyfr, tyle właśnie cykli zajmie wykonanie na niej operacji O (2 ^ n). Z O (2 ^ sqrt (n)) spadasz do liczby z 30 cyframi. Różnica jest bardzo duża w przypadku dużych liczb na korzyść rozwiązania sqrt (dla 1 miliona elementów, czyli (liczba z 300 000 cyfr) * cykl procesora w porównaniu z (liczba z 300 cyframi) * cykl procesora).
Andy,

Odpowiedzi:

16

To interesujące pytanie. Na szczęście, gdy już wiesz, jak to rozwiązać, nie jest to szczególnie trudne.

Dla funkcji f : NR + i g : NR + mamy fO ( g ) tylko wtedy, gdy lim sup n → ∞ f ( n ) / g ( n ) ∈ R .

Funkcja f : NR + ma co najwyżej wzrost wielomianowy wtedy i tylko wtedy, gdy istnieje stała kN taka, że fO ( nn k ). Praca Zróbmy to się arbitralne, ale stałej kN .

lim sup n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ e log (2) n 1/2 / e log ( n ) k =
lim n → ∞ e log (2) n 1/2 - log ( n ) k = ∞ ∉ R

Pierwsza równość jest prawdziwa, ponieważ zarówno nominator, jak i mianownik są monotonicznie rosnącymi stałymi funkcjami. Druga równość wykorzystuje tożsamość x y = e log ( x ) y . Limit nie jest skończony, ponieważ wykładnik w wyrażeniu końcowym nie jest ograniczony powyżej. Bez formalnego dowodu można założyć, że wiadomo, że n 1/2 dominuje log ( n ) asymptotycznie. Dlatego omawiana funkcja przekracza wzrost wielomianowy.

Jednak jego wzrost jest ściśle mniejszy niż wykładniczy, gdzie wykładniczy jest zdefiniowany (w tym celu przeze mnie) jako O ( n ↦ 2 c n ) dla c > 0. Wykazanie tego jest jeszcze bardziej proste.

lim sup n → ∞ 2 c n / 2 ( n 1/2 ) = lim n → ∞ 2 c n - n 1/2 = ∞ ∉ R

dla dowolnego ustalonego c > 0. Dlatego złożoność funkcji jest gdzieś naprawdę pomiędzy wielomianem a wykładnikiem.

5gon12eder
źródło
6

Jak duże to jest? Cóż, O (2 ^ sqrt (n)) jest dokładnie jak duży jest :-(

Aby dowiedzieć się, co to znaczy, wyobraź sobie, że twój algorytm nie byłby tylko O ​​(2 ^ sqrt (n)), ale że faktycznie zajmuje dokładnie 2 ^ sqrt (n) nanosekund na twoim komputerze:

n = 100: 2 ^ 10 = 1024 nanosekund. Kompletny brak czasu. n = 1000: 2 ^ 31,xxx = 2 miliardy nanosekund. Dwie sekundy, to zauważalne. n = 10 000: 2 ^ 100 ≈ 10 ^ 30 nanosekund = 10 ^ 21 sekund = 30 bilionów lat.

Jest to o wiele lepsze niż 2 ^ n nanosekundy, gdzie n = 100 zajęłoby 30 trylionów lat, ale wciąż rozmiar problemów, które można rozwiązać, jest dość ograniczony. Jeśli uważasz, że problem można rozwiązać, jeśli komputer może go rozwiązać w ciągu jednego tygodnia, to około 6 x 10 ^ 14 nanosekund, czyli około n = 2400. Z drugiej strony, do n = 400 można rozwiązać w ciągu milisekundy.

(W praktyce dla n = 10 000 zarówno O (2 ^ sqrt (n)), jak i O (2 ^ n) zajmują dokładnie ten sam czas: zbyt długo, aby na nie poczekać.)

Przekracza dowolny wielomian. Weź inny algorytm zajmujący n ^ 1000 sekund. Co jest praktycznie nierozwiązywalne dla n = 2. Ten algorytm trwa dłużej, zanim n wyniesie około 885 milionów. Ale tak naprawdę, kogo to obchodzi? W tym momencie liczba lat, które zajmują oba algorytmy, wynosi 9 000 cyfr.

gnasher729
źródło