8
En considérant O (log (N)) pour la complexité temporelle, quelle est la base de log?Quelle est la base du logarithme aux fins des algorithmes?
A
Répondre
15
Tous les logarithmes sont liés par une constante. (D'où le change-of-base formula). Parce que nous ne tenons généralement pas compte des constantes dans l'analyse de complexité, la base n'a pas d'importance.
Habituellement, la base est considérée comme 2, lors de la dérivation de l'algorithme. Considérez un genre comme merge sort. Vous pouvez en construire un tree, et l'arbre a une hauteur de log₂ n, car chaque nœud a deux branches.
+0
Je voudrais gras face à la deuxième phrase du premier paragraphe ("la base n'a pas d'importance") pour en faire une meilleure réponse. –
10
Peu importe, la complexité relative est la même quelle que soit la base utilisée.
+0
Hmmm. Si vous étendez logiquement cette instruction, vous diriez que O (n^2) est la même complexité relative que O (n^3). –
+0
Pas du tout. Big diff entre 1 million de carrés ou en cubes. Mais log2, log10, log100? Pas beaucoup de différence du tout. – cletus
+0
@Andrew Shepherd - Ce n'est pas correct. log_a (2n)/log_a (n) = log_b (2n)/log_b (n) pour a et b – mob
1
Une façon de penser est que O (log 2 X) = O (log X) = O (log N X)
Questions connexes
- 1. Quelle est la meilleure approche pour interpréter une entrée de texte à des fins de géocodage?
- 2. Ressources du débutant/introduction aux algorithmes de classification
- 3. Quelle est la plus grande base de données libre pour le moteur SQL Server disponible à des fins de test?
- 4. Logarithme inexact en Python
- 5. Programmation fonctionnelle pour les algorithmes de base
- 6. Créer une erreur d'intégrité pour une base de données SQL Server aux fins de test
- 7. Staff Alignement des algorithmes
- 8. Quelle est la meilleure approche d'automatisation des tests pour WatiN
- 9. Trouver l'exposant n = 2 ** x en utilisant des opérations au niveau du bit [logarithme en base 2 de n]
- 10. Big O complexité des opérations arithmétiques de base
- 11. Estimation du système d'équations simultanées avec des algorithmes génétiques
- 12. Logarithme népérien sur ActionScript 2?
- 13. Quelle base de données NoSQL à quelles fins? [Grand ro data]
- 14. Efficacité spatiale des algorithmes
- 15. Analyse des algorithmes (complexité)
- 16. Principes de base et maths requis pour les algorithmes
- 17. Quelle est la pratique du plugin jQuery?
- 18. Quelle est la fiabilité de la réplication du serveur SQL?
- 19. Aux experts: Quelle est la différence dans ce code?
- 20. Quelle est la sortie du code suivant?
- 21. Comment obtenir le logarithme de base 10 d'un Fixnum en Ruby?
- 22. Comment accéder aux classes d'un autre ensemble à des fins de tests unitaires?
- 23. Quelle est la différence entre la couche d'accès aux données et l'objet d'accès aux données?
- 24. Quelle est la meilleure pratique pour restreindre des pages spécifiques aux utilisateurs connectés uniquement dans Codeigniter?
- 25. Quelle est la différence entre la couche d'abstraction de la base de données et la couche d'accès aux données?
- 26. Quelle est la bonne utilisation du menu.addIntentOptions()?
- 27. R logarithme logarithmique multi-étiquettes Libellé Problème
- 28. Quelle est la signification de « xsd:?. La base d'extension = ....
- 29. Quelle est la meilleure façon d'ajouter un ID utilisateur aux entrées du journal RubyOnRails?
- 30. Quelle est l'alternative aux curseurs pour extraire de grandes quantités de données d'une base de données?
en double de: http: // stackoverflow. com/questions/1569702/is-big-ologn-log-base-e – outis