Czy podstawa dziennika Big O (logn) jest e?

97

W przypadku struktur danych typu drzewo wyszukiwania binarnego widzę, że notacja Big O jest zwykle oznaczana jako O (logn). Czy z małą literą „l” w logarytmie oznacza to logarytm o podstawie e (n), zgodnie z opisem logarytmu naturalnego? Przepraszam za proste pytanie, ale zawsze miałem problem z rozróżnieniem różnych logarytmów domniemanych.

math binary-tree complexity-theory big-o BuckFilledPlatypus
źródło
58
Jak przekonywali inni, to nie ma znaczenia. Wszystkie logarytmy różnią się od siebie stałą zależną tylko od użytych zasad. Ponieważ te czynniki są stałymi, nie mają one znaczenia dla celów analizy asymptotycznej. Po drugie, jeśli chodzi o określenie implikowanej podstawy, zależy to od kontekstu. Jako ogólną praktyczną regułę zastosuj następujące: 1. Kiedy matematyk pisze log n, ma na myśli logarytm naturalny. 2. Kiedy informatyk pisze, log nma na myśli podstawę dwa. 3. Kiedy inżynier pisze log n, ma na myśli dziesiątkę. Są to zwykle prawdziwe.
jason
4
@Jason, kolejną konwencją (w matematyce) jest to, że ln n oznacza logarytm naturalny, a log n jest podstawą dziesiątki. Think ln oznacza francuskie „logarithm naturelle”.
Internet man
2
Podstawą logarytmu jest liczba dzieci, które ma każdy węzeł. Jeśli jest to drzewo binarne, jest to dziennik o podstawie 2.
Paul
3
Doceniam twoją odpowiedź, Jason, i jest coś do przemyślenia. Kiedy badałem, na jakiej podstawie jest log (założyłem 2), zobaczyłem tę samą odpowiedź: że to nie ma znaczenia, ponieważ możesz wyeliminować stałą, log_10 (2). Mój problem z tym polega na tym, że na przykład: 5 log_10 (5) <5, podczas gdy 5 log_2 (5)> 5. Wprowadziłem je szybko w moim obliczeniu, aby pomóc w pojęciu, gdzie O (n logn) ma lepszy lub gorszy czas działania niż O (n). W zależności od podstawy ma to znaczenie. Dlatego naprawdę uważam, że WŁAŚCIWĄ odpowiedzią na to powinno być to, że kontekstowo log oznacza podstawę 2 w większości aplikacji informatycznych.
Doug Mead
@jason, powiedziałbym, że łatwiej jest użyć ln (interpretacja matematyka);). Pozostałe dwa przykłady są rozsądne.
belford

Odpowiedzi:

78

Raz wyrażone w notacji duże-O (), oba są poprawne. Jednak podczas wyprowadzania wielomianu O (), w przypadku wyszukiwania binarnego , tylko log 2 jest poprawny. Zakładam, że to rozróżnienie było intuicyjną inspiracją dla twojego pytania.

Ponadto, moim zdaniem, napisanie O (log 2 N) jest lepsze dla twojego przykładu, ponieważ lepiej przekazuje wyprowadzenie czasu działania algorytmu.

W notacji duże-O () stałe czynniki są usuwane. Konwersja z jednej podstawy logarytmu do innej polega na pomnożeniu przez stały współczynnik.

Zatem O (log N) jest równoważne O (log 2 N) ze względu na stały współczynnik.

Jeśli jednak możesz łatwo wpisać log 2 N w swojej odpowiedzi, zrobienie tego jest bardziej pedagogiczne. W przypadku wyszukiwania drzew binarnych masz rację, że log 2 N jest wprowadzany podczas wyprowadzania środowiska uruchomieniowego big-O ().

Przed wyrażeniem wyniku w notacji duże-O () różnica jest bardzo ważna. Podczas wyprowadzania wielomianu, który ma być przekazany za pomocą notacji duże-O, niepoprawne byłoby w tym przykładzie użycie logarytmu innego niż log 2 N przed zastosowaniem notacji O (). Gdy tylko wielomian zostanie użyty do przekazania najgorszego przypadku środowiska uruchomieniowego za pomocą notacji big-O (), nie ma znaczenia, jaki logarytm zostanie użyty.

Heath Hunnicutt
źródło
4
Ale bardzo łatwo jest pokazać, że log_2 njest to możliwe Θ(log_a n)dla każdej bazy a, więc nie jestem pewien, czy użycie podstawy 2 jest „bardziej poprawne”.
bcat
1
Kinopkio i bcat, dzięki za pomoc. Na początku nie było dobrze napisane. :)
Heath Hunnicutt
2
Cóż, dodałem jasności, ale jestem zraniony, że uważasz, że moja odpowiedź może zmylić ludzi. W rzeczywistości większość odpowiedzi tutaj nie uwzględniała intuicji OP i starała się go wiele nauczyć. Konkurencja mnie nie zachwyca, jest mi trochę smutno na niskim pasku pedagogicznym.
Heath Hunnicutt
11
„podczas wyprowadzania wielomianu O (), w przypadku wyszukiwania binarnego tylko log2 jest poprawne”. -1 dla słabej matematyki. Definicja x (n) ~ O (f (n)) mówi, że istnieje stała c taka, że ​​c * (f (n)) <x (n) dla wszystkich n> n_0. Dlatego stały współczynnik jest całkowicie nieistotny podczas analizy.
rlbond
3
Ponieważ log2 (x) jest równe log10 (x) / log10 (2), możesz wyprowadzić to w dowolny sposób. Dziennik w żadnym momencie nie ma ściśle podstawy 2.
rlbond
80

Na notację dużego O nie ma wpływu podstawa logarytmiczna, ponieważ wszystkie logarytmy w różnych bazach są powiązane przez stały współczynnik , O(ln n)jest równoważny O(log n).

wprowadź opis obrazu tutaj

Cade Roux
źródło
2
grafika jest zgrabna, ale pomyśl o wyprowadzeniu O () - wielomianu ... przed zastosowaniem O () tylko log-base-2 jest poprawny dla wyszukiwania binarnego.
Heath Hunnicutt
1
@Heath Hunnicutt: Nie. log_2 xRóżni się od log_b xstałego współczynnika c(b)dla dowolnej bazy bniezależnej od x.
jason
4
Ale dlaczego o tym mówisz, skoro nie ma to żadnego związku z pytaniem, a jedynie wprowadza w błąd?
hobbs
4
Hobbs: Ponieważ właśnie ten fakt jest powodem, dla którego OP został zainspirowany do zbadania. Staram się połączyć jego pomysły z odpowiedzią, aby rozumiał, dlaczego miał swoją intuicję, dlaczego nie ma to zastosowania do O (), ale nie nadużywać tego, czego się tutaj nauczył, do części pochodnej analizy. Zwięzłe odpowiedzi, które nie odnoszą się do pierwotnej przyczyny nieporozumienia, mogą prowadzić do dalszych nieporozumień. To zła pedagogika.
Heath Hunnicutt
4
@Heath Hunnicutt: Jeśli wykonujesz analizę asymptotyczną, nie ma to znaczenia. To, że czekasz do ostatniej minuty, aby wrzucić kilka dużych O, nie zmienia faktu, że mogę pomnożyć i podzielić wszystkie moje logarytmy przez jakąś głupią stałą i zmienić podstawę na każdym kroku. To znaczy, jeśli mam jakąś analizę, która obejmuje log_2 n, mogę po prostu wejść i zastąpić ją log_2 nwszędzie, log_pi 2 * log_2 n / log_pi 2a następnie po prostu skończyć z analizą, która jest log_pi 2 * log_pi nwszędzie. Teraz moja analiza dotyczy log_pi n.
jason
9

Tak naprawdę nie ma znaczenia, jaka to podstawa, ponieważ notacja duże-O jest zwykle zapisywana pokazując tylko asymptotycznie najwyższy rząd n, więc stałe współczynniki spadną. Ponieważ inna podstawa logarytmu jest równoważna stałemu współczynnikowi, jest zbędna.

To powiedziawszy, prawdopodobnie założyłbym, że podstawa dziennika 2.

Daniel Pryden
źródło
@Kinopiko: Co dokładnie jest w tym złego? Dokładniej, czym moja odpowiedź faktycznie różni się od twojej i innych tutaj?
Daniel Pryden,
Ach, może mój błąd w użyciu „współczynnika”. Będę edytować, aby wyjaśnić.
Daniel Pryden,
To był mój główny problem z twoją odpowiedzią. Nie jest też jasne, co masz na myśli, mówiąc „nadal będą miały pewien wpływ”. Jakiś wpływ na co?
bcat
1
Twoja odpowiedź omawia współczynniki najwyższego rzędu. To, co powiedziałeś, jest poprawne, ale to nie jest powód, dla którego podstawa logarytmu jest nieistotna. Powodem jest to, że różnica między różnymi logarytmami podstawowymi jest stałą, która jest pochłaniana przez O ().
1
@Kinopiko: OK. Myślę, że mówimy to samo. Powiedziałbym, że O (100) = O (1), ponieważ O (100) = O (100 * 1) = O (C * 1) = O (1). I to właśnie miałem na myśli, mówiąc, że ciągłe wyrażenia są zbyteczne. Oznacza to, że zamówienie z każdej stałej wynosi 1.
Daniel Pryden
7

Obie są poprawne. Pomyśl o tym

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))
cartonn
źródło
3

Tak, mówiąc o notacji duże-O, baza nie ma znaczenia. Jednak obliczeniowo w obliczu prawdziwego problemu z wyszukiwaniem ma to znaczenie.

Rozwijając intuicję dotyczącą struktur drzewiastych, warto zrozumieć, że drzewo wyszukiwania binarnego można przeszukiwać w czasie O (n log n), ponieważ jest to wysokość drzewa - to znaczy w drzewie binarnym z n węzłami drzewo głębokość wynosi O (n log n) (podstawa 2). Jeśli każdy węzeł ma troje dzieci, drzewo można nadal przeszukiwać w czasie O (n log n), ale z logarytmem o podstawie 3. Z punktu widzenia obliczeń liczba elementów podrzędnych każdego węzła może mieć duży wpływ na wydajność (patrz na przykład: tekst łącza )

Cieszyć się!

Paweł

Paweł
źródło
chciałeś powiedzieć, że wysokość drzewa binarnego to log n, a nie n log n, prawda?
komórka
1

Technicznie podstawa nie ma znaczenia, ale ogólnie można o niej myśleć jako o podstawie-2.

Tim Sylvester
źródło
1

Najpierw musisz zrozumieć, co to znaczy, że funkcja f (n) jest O (g (n)).

Formalna definicja jest następująca: * Mówi się, że funkcja f (n) jest O (g (n)) iff | f (n) | <= C * | g (n) | ilekroć n> k, gdzie C i k są stałymi. *

niech f (n) = log o podstawie a od n, gdzie a> 1 i g (n) = log o podstawie b z n, gdzie b> 1

UWAGA: Oznacza to, że wartości a i b mogą mieć dowolną wartość większą niż 1, na przykład a = 100 i b = 3

Teraz otrzymujemy: log o podstawie a od n mówi się, że jest O (podstawa log b z n) iff | podstawa loga a z n | <= C * | log o podstawie b z n | kiedykolwiek n> k

Wybierz k = 0 i C = log o podstawie a z b.

Teraz nasze równanie wygląda następująco: | log o podstawie a od n | <= log o podstawie a z b * | log o podstawie b z n | zawsze, gdy n> 0

Zwróć uwagę na prawą stronę, możemy manipulować równaniem: = log o podstawie a z b * | log o podstawie b z n | = | loguj podstawę b z n | * log o podstawie a z b = | log o podstawie a z b ^ (log o podstawie b z n) | = | log o podstawie a n |

Teraz nasze równanie wygląda następująco: | log o podstawie a od n | <= | log o podstawie a n | zawsze, gdy n> 0

Równanie jest zawsze prawdziwe bez względu na wartości n, b lub a, poza ich ograniczeniami a, b> 1 i n> 0. Zatem logarytm o podstawie a od n wynosi O (o podstawie b od n), a ponieważ a, b nie ma znaczenia, możemy je po prostu pominąć.

Możesz zobaczyć wideo na YouTube tutaj: https://www.youtube.com/watch?v=MY-VCrQCaVw

Możesz przeczytać artykuł na ten temat tutaj: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

tempmail
źródło