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)
Powiązane problemy
- 1. Wizualizacja algorytmów dla C#
- 2. Biblioteki algorytmów genetycznych dla Scala
- 3. Wprowadzanie próbek dla różnych algorytmów
- 4. Dla celów metrycznych Kademlia XOR
- 5. Jakie pakiety algorytmów szyfrowania mają być włączone dla gniazda SSL?
- 6. Podstawa quickblox Zły znacznik czasu dla 4.1.2
- 7. Podstawa dekodowania64 Strumień obrazu
- 8. Kolekcja algorytmów okluzji
- 9. owijania Intent w LabeledIntent dla celów wyświetlania
- 10. Wyliczenie wyszukujące dla celów interfejsu użytkownika
- 11. Najbliższa para algorytmów punktów
- 12. Algorytm listy algorytmów - Wywiad
- 13. Fałszywe otwarte ID dla celów testowych
- 14. XCode Różne zasoby dla różnych celów
- 15. Generowanie kluczy algorytmów RSA
- 16. SCRIPT_PATH = "$ {BASH_SOURCE [0]}" Zła podstawa
- 17. Obliczanie logarytmu za pomocą Windows 7 Kalkulator
- 18. Obliczanie logarytmu Base-n w Ruby
- 19. Czy Swift ma wbudowaną funkcję logarytmu?
- 20. C dla programistów R - zalecane zasoby/podejścia, gdy minie podstawa
- 21. Wybór turniejów algorytmów genetycznych
- 22. Jaka jest zalecana implementacja Bcrypt C?
- 23. Rails3: Podstawa # after_update została zaniechana
- 24. kątowa podstawa 2 dostęp href
- 25. Analiza algorytmów (złożoności)
- 26. CSS flex-podstawa nie działa, gdy flex-kierunek jest „Kolumna”
- 27. Analiza dwóch algorytmów Big-O
- 28. UISegmentedControl i dodawanie celów
- 29. Jaka jest najlepsza książka bioinformatyczna dla informatyka?
- 30. Jaka jest nazwa dla tego typu operatorów: '+ =', '- ='
duplikat: http: // stackoverflow. com/questions/1569702/is-big-ologn-log-base-e – outis