Algorytmiczna intuicja dla złożoności logarytmicznej

Wydaje mi się, że mam rozsądne pojęcie o złożoności takiej jak , Θ ( n ) i Θ ( n 2 ) .$\mathcal{O}(1)$$\Theta(n)$$\Theta(n^2)$

Jeśli chodzi o listę, to ciągłe wyszukiwanie, więc po prostu dostaje się na czele listy. Θ ( n ) , gdzie będę chodzić całą listę, a Θ ( n 2 ) idzie listę raz dla każdego elementu listy.$\mathcal{O}(1)$$\Theta(n)$$\Theta(n^2)$

Czy istnieje podobny intuicyjny sposób uchwycenia inny niż po prostu wiedza, że ​​leży gdzieś pomiędzy O ( 1 ) a Θ ( n ) ?$\Theta(\log n)$$\mathcal{O}(1)$$\Theta(n)$

złożony jest zwykle połączony z podziału. Korzystając z list jako przykładu, wyobraź sobie listę, której elementy są posortowane. Możesz przeszukiwać tę listę w czasie O ( log n ) - tak naprawdę nie musisz patrzeć na każdy element ze względu na posortowany charakter listy.$\Theta(\log n)$$\mathcal{O}(\log n)$

Jeśli spojrzysz na element na środku listy i porównasz go z elementem, którego szukasz, możesz od razu powiedzieć, czy leży on w lewej czy prawej połowie tablicy. Następnie możesz wziąć tę połowę i powtórzyć procedurę, aż znajdziesz ją lub dojdziesz do listy z 1 przedmiotem, który trywialnie porównujesz.

Widać, że lista skutecznie zmniejsza o połowę każdy krok. Oznacza to, że jeśli otrzymasz listę o długości , maksymalna liczba kroków, które musisz osiągnąć, aby dotrzeć do listy jednego elementu, to 5 . Jeśli masz listę 128 = 2 7 elementów, potrzebujesz tylko 7 kroków, dla listy 1024 = 2 10 potrzebujesz tylko 10 kroków itp.$32$$5$$128 = 2^7$$7$$1024 = 2^{10}$$10$

Jak widać, wykładnik w 2 n zawsze pokazuje liczbę kroków potrzebnych. Logarytm służy do „wyodrębnienia” dokładnie tej liczby wykładniczej, na przykład log 2 2 10 = 10 . Uogólnia również, aby wyświetlać długości, które nie są potęgami dwóch długości.$n$$2^n$$\log_2 2^{10} = 10$

W kategoriach (zrównoważonych) drzew (powiedzmy, drzewa binarnego, więc wszystkie są podstawą 2):$\log$

• pobiera korzeń drzewa$\Theta(1)$
• to przejście od korzenia do liścia$\Theta(\log n)$
• przemierza wszystkie węzły drzewa$\Theta(n)$
• to działania na wszystkich podzbiorach dwóch węzłów w drzewie, np. Liczba różnych ścieżek między dowolnymi dwoma węzłami.$\Theta(n^2)$
• - uogólnienie powyższego dla dowolnego podzbioru k węzłów (dla stałej k )$\Theta(n^k)$$k$$k$
• jest działaniem na wszystkie możliwe podzbiory węzłów (podzbiory wszystkich możliwych rozmiarów, tj. K = 1 , 2 , … , n .). Na przykład liczba różnychpoddrzewadrzewa.$\Theta(2^n)$$k=1,2, \ldots, n$

Aby było możliwe, musisz być w stanie zmniejszyć rozmiar problemu proporcjonalnie o pewną dowolną wartość w stosunku do n przy stałej operacji czasu.$O(\log n)$$n$

Na przykład w przypadku wyszukiwania binarnego można zmniejszyć rozmiar problemu o połowę przy każdej operacji porównania.

Czy musisz teraz zmniejszyć problem o połowę, a właściwie nie. Algorytmem jest nawet jeśli może on zmniejszyć przestrzeń wyszukiwania problemów o 0,0001%, o ile procent i operacja, której używa do zmniejszenia rozmiaru problemu, pozostaje stała, jest to algorytm O ( log n ) , nie będzie to szybki algorytm, ale nadal jest to O ( log n ) z bardzo dużą stałą. (Zakładając, że mówimy o log n z logiem base 2)$O(\log n)$$O(\log n)$$O(\log n)$$\log n$

Pomyśl o algorytmie konwertującym liczbę dziesiętną na binarną$n$

while n != 0:
   print n%2, 
   n = n/2

Ta whilepętla uruchamia razy.$\log(n)$

Tak, jest między 1 a n , ale jest bliższy 1 niż n . Co to jest log ( n ) ? Funkcja log jest odwrotną funkcją potęgowania. Zacznę od potęgowania, a powinieneś lepiej zrozumieć, czym jest logarytm.$\log(n)$$1$$n$$1$$n$$\log(n)$

Rozważ dwie liczby, i 2 100 . 2 100 to 2 pomnożone ze sobą 100 razy. Możesz z pewnym wysiłkiem policzyć 100 liczb, ale czy możesz policzyć 2 100 ? Założę się, że nie możesz. Dlaczego? 2 100 to tak duża liczba, że ​​jest większa niż liczba wszystkich atomów we wszechświecie. Zastanów się przez chwilę. Jest to tak duża liczba, że ​​pozwala nadać każdemu atomowi nazwę (liczbę). A liczba atomów w twoim paznokciu jest prawdopodobnie rzędu miliardów. 2 100 powinno wystarczyć dla każdego (gra słów :).$100$$2^{100}$$2^{100}$$2$$100$$100$$2^{100}$$2^{100}$$2^{100}$

Teraz między dwiema liczbami, i 2 100 , 100 jest logarytmem 2 100 (w bazie 2 ). 100 to stosunkowo niewielka liczba niż 2 100 . Każdy powinien mieć w domu 100 różnych przedmiotów. Ale 2 100 jest wystarczające dla wszechświata. Myśl o domu a wszechświecie, myśląc o log ( n ) i n .$100$$2^{100}$$100$$2^{100}$$2$$100$$2^{100}$$100$$2^{100}$$\log(n)$$n$

Skąd się bierze potęgowanie i logarytmy? Dlaczego tak bardzo interesują się informatyką? Możesz tego nie zauważyć, ale potęgowanie jest wszędzie. Czy zapłaciłeś odsetki od karty kredytowej? Właśnie zapłaciłeś wszechświatowi za swój dom (nie tak źle, ale krzywa pasuje). Lubię myśleć, że potęgowanie wynika z reguły produktu, ale inni mogą podać więcej przykładów. Jaką zasadę produktu możesz zapytać; I odpowiem.

Załóżmy, że masz dwa miasta i B , a są między nimi dwa sposoby. Jaka jest liczba ścieżek między nimi? Dwa. To jest banalne. Powiedzmy teraz, że istnieje inne miasto C i możesz przejść z B do C na trzy sposoby. Ile jest teraz ścieżek między A i C ? Sześć, prawda? Jak to zdobyłeś? Policzyłeś je? A może ich pomnożyłeś? Tak czy inaczej, łatwo zauważyć, że oba sposoby dają podobny wynik. Teraz, jeśli dodasz miasto D, do którego można dotrzeć z C na cztery sposoby, ile jest dróg między A i $A$$B$$C$$B$$C$$A$$C$$D$$C$$A$$D$? Policz, jeśli mi nie ufasz, ale równa się czyli 24 . Teraz, jeśli jest dziesięć miast i są dwie ścieżki z jednego miasta do drugiego, i są ułożone tak, jakby były na linii prostej. Ile jest ścieżek od początku do końca? Pomnóż je, jeśli mi nie ufasz, ale powiem ci, że są 2 10 , czyli 1024 . Zobacz, że 2 10 jest wykładniczym wynikiem 10 , a 10 jest logarytmem 2 10 . 10 to mała liczba w porównaniu do 1024 .$2\cdot 3\cdot 4$$24$$2^{10}$$1024$$2^{10}$$10$$10$$2^{10}$$10$$1024$

Funkcja logarytm jest n co n jest 2 n (zauważ, że 2 jest podstawa logarytmu jest). Jeśli zwielokrotnisz log b ( n ) ze sobą b razy (zauważ, że b jest podstawą logarytmu), otrzymasz n . log ( n ) jest tak mały, tak mały w porównaniu z n , że jest wielkości twojego domu, gdzie n jest wielkością wszechświata.$\log_2(n)$$n$$n$$2^n$$2$$\log_b(n)$$b$$b$$n$$\log(n)$$n$$n$

Praktycznie rzecz biorąc, funkcje działają bardzo podobnie do funkcji stałych. Rosną z n , ale rosną bardzo powoli. Jeśli zoptymalizowałeś program do działania w czasie logarytmicznym, który zajmował dzień wcześniej, prawdopodobnie uruchomisz go w kolejności minut. Sprawdź sam problemy z Project Euler.$\log(n)$$n$

Aby kontynuować Twój motyw, jest jak wielokrotne zgadywanie gdzie x znajduje się na liście i mówienie „wyżej” lub „niżej” (pod względem indeksu).$O(\log n)$$x$

Nadal opiera się na wielkości listy, ale wystarczy odwiedzić tylko ułamek elementów.

Jeśli mamy algorytm dzielenia i zdobywania i wykonujemy tylko jedno rekurencyjne wywołanie podproblemu, a jest to drugi przypadek w twierdzeniu Master , tzn. Złożoność czasowa części nierekurencyjnej wynosi , wówczas złożoność algorytmu wyniesie Θ ( lg k + 1 n ) .$\Theta(\lg^k n)$$\Theta(\lg^{k+1} n)$

Innymi słowy, gdy mamy algorytm dziel i zwyciężaj z jednym wywołaniem rekurencyjnym do samego problemu z rozmiarem, stałym czynnikiem obecnego problemu, a czas w części nierekurencyjnej wynosi (stały), to czas działania algorytmu wyniesie lg n .$\Theta(1)$$\lg n$

Wyszukiwania binarnego algorytm jest klasycznym przykładem.

Intuicja mówi, ile razy można zmniejszyć liczbę o połowę, powiedzmy n, zanim zostanie zmniejszona do 1, to O (lg n).

Aby wizualizować, spróbuj narysować je jako drzewo binarne i policz liczbę poziomów, rozwiązując ten postęp geometryczny.

2^0+2^1+...+2^h = n