Pour les binaires de recherche un arbre du type de structures de données, je vois le Big O la notation est généralement noté que O(logn). Avec une minuscule " l " dans le journal, est ce que cela implique logarithme de base e (n) tel que décrit par le logarithme naturel? Désolé pour la question simple mais j'ai toujours eu de la difficulté à distinguer entre les différents implicite des logarithmes.
Réponses
Trop de publicités?
Cade Roux
Points
53870
Big O la notation n'est pas affecté par logarithmique de base, parce que tous les logarithmes dans différentes bases sont liées par un facteur constant, O(ln n) est équivalent à O(log n)
Une fois exprimées en big-O() notation, les deux sont corrects. Cependant, au cours de la dérivation de l'O() polynôme, dans le cas des binaires de recherche, seul le journal des2 est correcte. Je suppose que cette distinction était intuitive, l'inspiration pour votre question pour commencer.
Aussi, comme une question de mon avis, écrit O(log2 N) est la meilleure pour votre exemple, parce qu'il communique mieux la dérivation de l'algorithme au moment de son exécution.
En big-O() notation, des facteurs constants sont supprimés. La conversion d'un logarithme en base à une autre implique de multiplier par un facteur constant.
Donc O(log N) est équivalent à O(log2 N) en raison d'un facteur constant.
Toutefois, si vous pouvez facilement composer des log2 N dans votre réponse, c'est plus pédagogique. Dans le cas d'un arbre binaire de recherche, il est exact que les log2 N est introduit lors de la dérivation de la grande-O() de l'exécution.
Avant d'exprimer le résultat en tant que big-O() notation, la différence est très importante. Lorsque calculer le polynôme d'être communiquées par l'intermédiaire de big-O de la notation, il serait incorrect de cet exemple pour utiliser un logarithme autres que log2 N, avant l'application de la O()-notation. Dès que le polynôme est utilisé pour communiquer de la pire cas d'exécution par big-O() notation, il n'a pas d'importance ce logarithme est utilisé.
Daniel Pryden
Points
22167
Il n'importe pas vraiment ce que c'est, depuis le big-O notation est généralement écrite indiquant uniquement le asymptotiquement la plus élevée de l'ordre de n, de sorte coefficients constants effaceront. Depuis un autre logarithme de base est équivalent à une constante coefficient, il est superflu.
Cela dit, je serais probablement prendre logarithme de base 2.
Tim Sylvester
Points
14047
Paul
Points
3767
Oui, quand on parle de big-O de notation, la base n'a pas d'importance. Cependant, le calcul lorsqu'ils sont confrontés à un véritable problème de recherche, il n'importe.
Lors du développement d'une intuition sur les structures en arbre, il est utile de comprendre qu'un arbre de recherche binaire peut être consulté en O(n log n) en temps parce que c'est la hauteur de l'arbre - qui est, dans un arbre binaire avec n nœuds, la profondeur de l'arbre est O(n log n) (base 2). Si chaque nœud a trois enfants, l'arbre peut toujours être recherché en O(n log n) le temps, mais avec une base 3 logarithme. De calcul, le nombre d'enfants de chaque nœud peut avoir un grand impact sur la performance (voir par exemple: texte du lien)
Profitez-en!
Paul
