Moje pytanie powstaje ze stanowiska "Plain English Explanation of Big O". Nie znam dokładnego znaczenia złożoności logarytmicznej. Wiem, że mogę dokonać regresji między czasem a liczbą operacji i obliczyć wartość X-kwadrat oraz określić złożoność. Chciałbym jednak poznać metodę szybkiego określenia na papierze.Jak sprawdzić, czy Big O jest logarytmiczny?
Jak określić złożoność logarytmiczną? Czy są jakieś dobre testy porównawcze?
Nie jestem pewien, czy to masz na myśli, ale ... złożoność logarytmiczna pojawia się zwykle, gdy pracujesz z rozłożoną strukturą danych, taką jak zbalansowane drzewo binarne, które zawiera 1 węzeł w katalogu głównym, 2 dzieci, 4 wnuków, 8 prawnuków itd. Zasadniczo na każdym poziomie liczba węzłów jest pomnożona przez pewien czynnik (2), ale nadal tylko jedna z nich jest zaangażowana w iterację. Lub jako kolejny przykład, pętla, w której indeks podwaja na każdym kroku:
for (int i = 1; i < N; i *= 2) { ... }
Takie rzeczy są podpisy logarytmicznej złożoności.
Master theorem zwykle działa.
Nieco trudne do pomyślenia, ale bardzo dobre, gdy opanujesz go. – samoz
Nie rygorystyczne, ale masz algorytm, który w zasadzie dzieli pracę wymaganą do wykonania przez połowę w każdej iteracji, wtedy masz złożoność logarytmiczną. Klasycznym przykładem jest wyszukiwanie binarne.
niekoniecznie. Rozumiem, co próbujesz implikować, ale tylko dlatego, że dzielisz pracę na pół, nie oznacza to logarytmicznej złożoności, możesz nawet mieć wykładniczy czas na tę kwestię. Należy również zwrócić uwagę na sposób rekombinacji rozwiązań i sposób rozwiązywania podzielonych problemów. Istnieje wiele przypadków, w których dominuje etap rekombinacji. Zobacz twierdzenie magisterskie lub lepiej rozwiązuj powtarzanie bez twierdzenia. Pod prostym powtarzaniem jest wiele niespodzianek. – unj2
@unjaan: Myślę, że źle mnie zrozumiałeś. Nie tylko powiedziałem, że dzieło dzieli się na pół, powiedziałem "praca musi być wykonana o połowę przy każdej iteracji". Chodzi mi o to, że jeśli na każdym kroku jest połowa pracy, którą trzeba wykonać w porównaniu z poprzednim krokiem, to masz logarytmiczną złożoność (dla pracy, odczytu obliczeń). –
Jeśli chcesz dowiedzieć się więcej o logarytmicznym Big Oh, bądź czujny, gdy twoje dane są przecinane o połowę na każdym kroku nawrotu.
Dzieje się tak dlatego, że jeśli przetwarzasz dane, które są 1/2 tak duże jak krok przed nim, jest to nieskończona seria.
Niekoniecznie 1/2.1/c działa, o ile "c" jest stałe. –
, ale 1/2 jest bardziej "intuicyjne" –
Zwykle, gdy mówimy o Big O, log oznacza log base 2. – samoz
Oto inny sposób powiedzenia tego.
Załóżmy, że Twój algorytm jest liniowy pod względem liczby cyfr w rozmiarze problemu. Być może masz nowy algorytm do liczenia dużej liczby, który możesz pokazać liniowo pod względem liczby cyfr. Dwudziestocyfrowa liczba zajmuje więc dwa razy więcej czasu niż 10-cyfrowy numer za pomocą twojego algorytmu. Miałoby to złożoność logów. (I byłoby to coś warte dla wynalazcy.)
Bisekcja ma to samo zachowanie. Wykonanie około 10 kroków bisekcji wymaga przecięcia długości odcinka o współczynnik 1024 = 2^10, ale tylko 20 kroków skróci ten przedział o współczynnik 2^20.
Złożoność logów nie zawsze oznacza, że algorytm jest szybki we wszystkich problemach. Współczynnik liniowy przed O (log (n)) może być duży. Tak więc twój algorytm może być okropny w przypadku małych problemów, nie przydaje się, dopóki rozmiar problemu nie jest znaczący, że inne algorytmy umierają w wyniku wykładniczej (lub wielomianowej) śmierci.
Dobrze objaśniony dużym rozmiarem problemu. –
+1 bardzo interesujące. Szukam czegoś bardziej podobnego do twoich przykładów. Czy algorytm jest logarytmiczny jako: dla (int i = BIG_number; i> N; i * = 1/2) {...} –
1/2 to zero w całkowitej liczbie podziałów, ale jeśli używasz "i/= 2" zamiast , Tak to jest. (Jeśli jest to konkretny algorytm, o który się zastanawiasz, dobrym pomysłem może być uwzględnienie go w pytaniu.) –