Est-ce que Big O (logn) log base e?

96

Pour le type d'arbre de recherche binaire des structures de données, je vois que la notation Big O est généralement notée O (logn). Avec un «l» minuscule dans le log, cela implique-t-il un log de base e (n) comme décrit par le logarithme naturel? Désolé pour la question simple mais j'ai toujours eu du mal à distinguer les différents logarithmes implicites.

math binary-tree complexity-theory big-o BuckFilledPlatypus
la source

58

Comme d'autres l'ont souligné de manière convaincante, cela n'a pas d'importance. Tous les logarithmes diffèrent les uns des autres par une constante dépendant uniquement des bases impliquées. Comme ces facteurs sont des constantes, ils ne sont pas pertinents aux fins de l'analyse asymptotique. Deuxièmement, en ce qui concerne la détermination de la base implicite, cela dépend du contexte. En règle générale, utilisez ce qui suit: 1. Lorsqu'un mathématicien écrit, log nil entend le logarithme naturel. 2. Quand un informaticien écrit, log nil veut dire la base deux. 3. Quand un ingénieur écrit, log nil veut dire base dix. Celles-ci sont généralement vraies.

jason

4

@Jason, une autre convention (en mathématiques) est que ln n signifie le logarithme naturel et le log n est la base dix. Think ln signifie le «logarithme naturel» français.

Internet man

2

La base du logarithme est le nombre d'enfants de chaque nœud. S'il s'agit d'un arbre binaire, c'est un journal de base 2.

Paul

3

J'apprécie votre réponse, Jason, et voici quelque chose à penser. En recherchant dans quelle base se trouve le journal (j'ai supposé 2), j'ai vu la même réponse: que cela n'a pas d'importance car vous pouvez éliminer la constante, log_10 (2). Mon problème avec ceci est que, par exemple: 5 log_10 (5) <5 alors que 5 log_2 (5)> 5. Je les ai saisis rapidement dans mon calcul pour aider à conceptualiser où O (n logn) a un meilleur ou un pire temps d'exécution que O (n). Selon la base, cela importe. Par conséquent, je pense vraiment que la bonne réponse à cela devrait être que le journal signifie contextuellement la base 2 dans la plupart des applications informatiques.

Doug Mead

@jason, je dirais qu'il est plus facile d'utiliser ln (interprétation mathématicienne);). Les deux autres exemples sont raisonnables.

belford

77

Une fois exprimés en notation big-O (), les deux sont corrects. Cependant, lors de la dérivation du polynôme O (), dans le cas d' une recherche binaire , seul log ₂ est correct. Je suppose que cette distinction a été l'inspiration intuitive pour commencer votre question.

De plus, à mon avis, écrire O (log ₂ N) est préférable pour votre exemple, car il communique mieux la dérivation de l'exécution de l'algorithme.

En notation big-O (), les facteurs constants sont supprimés. La conversion d'une base logarithmique à une autre implique la multiplication par un facteur constant.

Donc O (log N) est équivalent à O (log ₂ N) en raison d'un facteur constant.

Cependant, si vous pouvez facilement composer le journal ₂ N dans votre réponse, cela est plus pédagogique. Dans le cas de la recherche d'arborescence binaire, vous avez raison de dire que log ₂ N est introduit lors de la dérivation du runtime big-O ().

Avant d'exprimer le résultat sous forme de notation big-O (), la différence est très importante. Lors de la dérivation du polynôme à communiquer via la notation big-O, il serait incorrect pour cet exemple d'utiliser un logarithme autre que log ₂ N, avant d'appliquer la notation O (). Dès que le polynôme est utilisé pour communiquer le pire des cas d'exécution via la notation big-O (), peu importe le logarithme utilisé.

Heath Hunnicutt
la source

4

Mais il est très facile de montrer que log_2 nc'est Θ(log_a n)pour n'importe quelle base a, donc je ne suis pas sûr de voir en quoi l'utilisation de la base 2 est "plus correcte".

bcat

1

Kinopkio et bcat, merci de l'avoir aidé à devenir utile. Ce n'était pas très bien écrit au début. :)

Heath Hunnicutt

2

Eh bien, j'ai ajouté de la clarté, mais je suis sûr que vous pensez que ma réponse pourrait semer la confusion chez les gens. En fait, la plupart des réponses ici ne tenaient pas compte de l'intuition du PO et essayaient de lui apprendre beaucoup. Je ne suis pas tellement impressionné par la concurrence, je suis un peu triste à la barre basse de la pédagogie.

Heath Hunnicutt

11

"lors de la dérivation du polynôme O (), dans le cas d'une recherche binaire, seul log2 est correct." -1 pour les mathématiques médiocres. La définition de x (n) ~ O (f (n)) dit qu'il existe une constante c telle que c * (f (n)) <x (n) pour tout n> n_0. Ainsi, le coefficient constant est totalement sans importance lors de l'analyse.

rlbond

3

Puisque log2 (x) est égal à log10 (x) / log10 (2), vous pouvez le dériver dans les deux cas. Le journal n'est à aucun moment strictement de base 2.

rlbond

80

La notation Big O n'est pas affectée par la base logarithmique, car tous les logarithmes dans différentes bases sont liés par un facteur constant , O(ln n)équivaut à O(log n).

Cade Roux
la source

2

les graphiques sont soignés mais pensez à la dérivation du polynôme O () - ... avant que O () ne soit appliqué, seul log-base-2 est correct pour la recherche binaire.

Heath Hunnicutt

1

@Heath Hunnicutt: Non log_2 xdiffère de log_b xpar un facteur constant c(b)pour toute base bindépendante de x.

jason

4

Mais pourquoi parlez-vous de cela, alors que cela n'a aucun rapport avec la question et ne sert qu'à confondre?

hobbs

4

Hobbs: Parce que c'est la raison pour laquelle le PO a été inspiré pour s'enquérir. J'essaie de relier ses idées à la réponse, afin qu'il comprenne pourquoi il a eu son intuition, pourquoi cela ne s'applique pas à O (), mais ne pas appliquer de manière excessive ce qu'il apprend ici à la partie dérivation de l'analyse. Les réponses laconiques qui ne s'attaquent pas à la cause profonde du malentendu peuvent conduire à d'autres malentendus. C'est une mauvaise pédagogie.

Heath Hunnicutt

4

@Heath Hunnicutt: Si vous faites une analyse asymptotique, cela n'a pas d'importance. Le fait d'attendre la dernière minute pour lancer des gros O ne change pas le fait que je peux multiplier et diviser tous mes logarithmes par une constante idiote et changer la base à toutes les étapes. Autrement dit, si j'ai une analyse qui implique log_2 n, je peux simplement entrer et remplacer log_2 npartout par log_pi 2 * log_2 n / log_pi 2et ensuite finir avec une analyse qui a log_pi 2 * log_pi npartout. Maintenant, mon analyse est en termes de log_pi n.

jason

9

La base n'a pas vraiment d'importance, car la notation big-O est généralement écrite en ne montrant que l'ordre asymptotiquement le plus élevé de n, donc les coefficients constants disparaîtront. Puisqu'une base logarithmique différente équivaut à un coefficient constant, elle est superflue.

Cela dit, je suppose probablement la base log 2.

Daniel Pryden
la source

@Kinopiko: Qu'est-ce qui ne va pas exactement? Plus précisément, en quoi ma réponse est-elle factuellement différente de la vôtre et des autres ici?

Daniel Pryden

Ah, peut-être mon erreur dans l'utilisation du "coefficient". Je vais éditer pour clarifier.

Daniel Pryden

C'était mon principal problème avec votre réponse. De plus, ce que vous entendez par «ils auront encore un certain effet» n'est pas clair. Un effet sur quoi?

bcat

1

Votre réponse traite des coefficients d'ordre le plus élevé. Ce que vous avez dit est correct pour autant, mais ce n’est pas la raison pour laquelle la base logarithmique n’est pas pertinente. La raison en est que la différence entre les différents logarithmes de base est une constante qui est absorbée par le O ().

1

@Kinopiko: OK. Je pense que nous disons la même chose. Je dirais O (100) = O (1) car O (100) = O (100 * 1) = O (C * 1) = O (1). C'est ce que j'entendais par les expressions constantes étant superflues. Autrement dit, l' ordre de toute constante est 1.

Daniel Pryden

7

Les deux sont corrects. Penses-y

log2(n)=log(n)/log(2)=O(log(n))
log10(n)=log(n)/log(10)=O(log(n))
logE(n)=log(n)/log(E)=O(log(n))

Cartonn
la source

2

Oui, quand on parle de notation big-O, la base n'a pas d'importance. Cependant, sur le plan informatique, face à un vrai problème de recherche, cela compte.

Lors du développement d'une intuition sur les structures arborescentes, il est utile de comprendre qu'un arbre de recherche binaire peut être recherché en temps O (n log n) car c'est la hauteur de l'arbre - c'est-à-dire dans un arbre binaire avec n nœuds, l'arbre la profondeur est O (n log n) (base 2). Si chaque nœud a trois enfants, l'arbre peut toujours être recherché en temps O (n log n), mais avec un logarithme de base 3. Sur le plan informatique, le nombre d'enfants que possède chaque nœud peut avoir un impact important sur les performances (voir par exemple: texte du lien )

Prendre plaisir!

Paul

Paul
la source

vous vouliez dire que la hauteur d'un arbre binaire est log n, pas n log n, non?

cellule

1

Techniquement, la base n'a pas d'importance, mais vous pouvez généralement la considérer comme base-2.

Tim Sylvester
la source

1

Vous devez d'abord comprendre ce que cela signifie pour une fonction f (n) d'être O (g (n)).

La définition formelle est: * Une fonction f (n) est dite O (g (n)) ssi | f (n) | <= C * | g (n) | chaque fois que n> k, où C et k sont des constantes. *

soit f (n) = log base a de n, où a> 1 et g (n) = log base b de n, où b> 1

REMARQUE: cela signifie que les valeurs a et b peuvent être n'importe quelle valeur supérieure à 1, par exemple a = 100 et b = 3

Nous obtenons maintenant ce qui suit: la base log a de n est dite O (base log b de n) ssi | base log a de n | <= C * | base log b de n | chaque fois que n> k

Choisissez k = 0 et C = base log a de b.

Maintenant, notre équation ressemble à ceci: | base log a de n | <= base log a de b * | base log b de n | chaque fois que n> 0

Maintenant, notre équation ressemble à ceci: | base log a de n | <= | base log a de n | chaque fois que n> 0

L'équation est toujours vraie quelles que soient les valeurs n, b ou a, autres que leurs restrictions a, b> 1 et n> 0. Donc la base log a de n est O (base log b de n) et comme a, b n'a pas d'importance, nous pouvons simplement les omettre.

Vous pouvez voir une vidéo YouTube dessus ici: https://www.youtube.com/watch?v=MY-VCrQCaVw

Vous pouvez lire un article à ce sujet ici: https://medium.com/@randerson112358/omitting-bases-in-logs-in-big-o-a619a46740ca

tempmail
la source

Est-ce que Big O (logn) log base e?

Réponses: