8
Mentre si considera O (log (N)) per la complessità temporale, qual è la base del registro?Qual è la base del logaritmo ai fini degli algoritmi?
A
risposta
15
Tutti i logaritmi sono correlati da alcune costanti. (Da qui il change-of-base formula). Poiché generalmente ignoriamo le costanti nell'analisi della complessità, la base non ha importanza.
Di solito, la base è considerata 2, quando si ricava l'algoritmo. Considera un tipo come merge sort. Puoi costruire un tree e l'albero ha un'altezza di log₂ n, perché ogni nodo ha due rami.
+0
Vorrei mettere in evidenza la seconda frase del primo paragrafo ("la base non ha importanza") per renderla una risposta ancora migliore. –
10
Non importa, la complessità relativa è la stessa indipendentemente dalla base utilizzata.
+0
Hmmm. Se estendete logicamente questa affermazione, direste che O (n^2) è la stessa complessità relativa di O (n^3). –
+0
Niente affatto. Grande diff tra 1 milione di quadrati o cubetti. Ma log2, log10, log100? Non c'è molta differenza. – cletus
+0
@Andrew Shepherd - Non è corretto. log_a (2n)/log_a (n) = log_b (2n)/log_b (n) per qualsiasi a e b – mob
1
Un modo di pensare di esso è che O (log X) = O (log X) = O (log N X)
Problemi correlati
- 1. Qual è la qualità casuale degli algoritmi Perlin/Simplex Noise?
- 2. Calcolo del logaritmo Base-n in Ruby
- 3. Calcolo logaritmo in base 2
- 4. Come può essere modificata la "data odierna" ai fini del test unitario?
- 5. Analisi degli algoritmi (complessità)
- 6. Qual è la specificità del selettore degli attributi?
- 7. Algoritmo logaritmo
- 8. Qual è la durata e la validità degli iteratori C++?
- 9. Funzione logaritmo di una base intera arbitraria in C
- 10. Algoritmo di logaritmo discreto
- 11. Recupera l'utente Windows corrente nell'applicazione Web Java EE ai fini del Single Sign-On
- 12. Algoritmi del grafico di apprendimento
- 13. Come funzionano 20 domande sugli algoritmi AI?
- 14. Quando una libreria condivisa è considerata "uguale" ai fini della condivisione?
- 15. qual è il motivo alla base del require_tree predefinito nella pipeline degli asset?
- 16. Perché un `switch` è considerato una struttura di loop ai fini di` continue`?
- 17. Programmazione funzionale per algoritmi di base
- 18. Qual è la precisione del mondo degli accelerometri del telefono quando viene utilizzato per il posizionamento?
- 19. Costruzione della chiave di cache in base al nome del metodo e ai valori degli argomenti
- 20. Qual è la logica alla base degli oggetti associati in Scala?
- 21. Schemi e algoritmi di progettazione per applicare regole ai fatti
- 22. Applicazioni degli algoritmi di Kruskal e Prim
- 23. Qual è il ragionamento alla base della sintassi degli spazi bianchi di Makefile?
- 24. Calcolo logaritmo veloce
- 25. Calcola il logaritmo in python
- 26. È possibile creare elenchi che si denominino in base ai nomi degli oggetti di input?
- 27. LL (*) rispetto ai parser PEG: qual è la differenza?
- 28. Algoritmi per la parallelizzazione del sistema di simulazione del tessuto?
- 29. Qual è la complessità asintotica dell'operazione GroupBy?
- 30. Qual è la lunghezza massima degli sms concatenati in smpp?
duplicati di: http: // StackOverflow. it/questions/1569702/is-big-ologn-log-base-e – outis