8
Rozważając O (log (N)) dla złożoności czasowej, jaka jest podstawa logu?Jaka jest podstawa logarytmu dla celów algorytmów?
A
Odpowiedz
15
Wszystkie logarytmy są powiązane przez pewną stałą. (Stąd change-of-base formula). Ponieważ zazwyczaj pomijamy stałe w analizie złożoności, podstawa nie ma znaczenia.
Zazwyczaj podstawa jest uważana za 2, gdy pochodzi z algorytmu. Zastanów się, jak w rodzaju merge sort. Możesz zbudować z niego tree, a drzewo ma wysokość log₂ n, ponieważ każdy węzeł ma dwie gałęzie.
+0
Chciałbym pogrubić twarz drugiego zdania w pierwszym akapicie ("baza nie ma znaczenia"), aby uczynić z niego jeszcze lepszą odpowiedź. –
10
Nie ma znaczenia, względna złożoność jest taka sama niezależnie od użytej bazy.
+0
Hmmm. Jeśli logicznie rozszerzysz tę instrukcję, powiedziałbyś, że O (n^2) ma taką samą względną złożoność jak O (n^3). –
+0
Wcale nie. Duża różnica między 1 milionem kwadratów lub sześcianem. Ale log2, log10, log100? Nie ma dużej różnicy. – cletus
+0
@Andrew Shepherd - To nie jest poprawne. log_a (2n)/log_a (n) = log_b (2n)/log_b (n) dla każdego a i b – mob
1
Jednym ze sposobów, aby myśleć o tym, że O (log x) = O (log x) = O (log N X)
duplikat: http: // stackoverflow. com/questions/1569702/is-big-ologn-log-base-e – outis