Signification de lg * n Dans L'analyse algorithmique
je suis en train de lire sur l'analyse algorithmique et j'ai lu qu'un certain algorithme (Union rapide pondérée avec compression de chemin) est d'ordre N + M lg * N. apparemment, bien que ce soit linéaire parce que lg * n est une constante dans cet univers. Quelle opération mathématique est mentionnée ici. Je ne suis pas familier avec la notation lg * N.
6 réponses
Les réponses apportées jusqu'ici sont faux. lg* n (lire "journal d'étoiles") est le logarithme itéré. Il est défini aussi récursivement que
0 if n <= 1
lg* n =
1 + lg*(lg n) if n > 1
une autre façon d'y penser est le nombre de fois où vous devez itérer le logarithme avant que le résultat soit inférieur ou égal à 1.
il pousse extrêmement lentement. Vous pouvez en lire plus sur Wikipédia qui contient quelques exemples d'algorithmes pour lg* n apparaît dans l'analyse.
je suppose que tu parles de l'algorithme analysé sur la diapositive 44 de cette conférence: http://www.cs.princeton.edu/courses/archive/fall05/cos226/lectures/union-find.pdf
où ils disent "lg * N est une constante dans cet univers" je crois qu'ils ne sont pas tout à fait littéraux. lg*N ne semble augmenter avec N selon leur table sur le côté droit de la diapositive; il se trouve juste à croître à un rythme si lent qu'il ne peut pas être considéré beaucoup d'autre (N = 2^65536 - > journal*n = 5). En tant que tel, il semble qu'ils disent que vous pouvez simplement ignorer le journal*N comme une constante, car il n'augmenteront jamais assez pour causer un problème.
je peux me tromper, cependant. C'est tout simplement la façon dont je l'ai lu.
edit: il peut être utile de noter que pour cette équation, ils définissent "lg*N" comme étant 2^(lg*(N-1)). Ce qui signifie qu'une valeur de 2^(2^(65536)) [un nombre beaucoup plus élevé] donnerait lg*N = 6, par exemple.
La définition récursive de lg*n par Jason est équivalent à
lg*n = m quand 2 II m <= n < 2 II (m+1)
où
2 II m=2^2^...^2 (exponentiation répétée, m copies de 2)
est la notation flèche double up de Knuth. Ainsi,
lg*2= 1, lg*2^2= 2, lg*2^{2^2}= 3, lg*2^{2^{2^2}} = 4, lg*2^{2^{2^{2^2}}} = 5.
Par conséquent lg*n = 4 pour 2^{16} <= N < 2^{65536}.
La fonction lg*n approche l'infini très lentement.
(Plus rapide que l'inverse de la fonction Ackermann A (n, n) ce qui implique n-2 flèches vers le haut.)
Etienne
lg est" LOG " ou exponentielle inverse. lg se réfère généralement à la base 2, mais pour l'analyse algorithmique, la base n'a généralement pas d'importance.
lg n renvoie à log base n. C'est la réponse à l'équation 2^x = N. Dans L'analyse de la complexité de Big O, La base de log n'est pas pertinente. Les puissances de 2 apparaissent en CS, donc ce n'est pas surprenant si nous devons choisir une base, ce sera la base 2.
un bon exemple de l'endroit où il apparaît est un arbre entièrement binaire de hauteur h, qui a 2 ^ h-1 noeuds. Si nous laissons n être le nombre de noeuds cette relation est l'arbre est la hauteur lg n avec n noeuds. L'algorithme qui traverse cet arbre prend au plus lg n à voir si une valeur est stockée dans l'arbre.
comme on pouvait s'y attendre, wiki a d'excellentes informations supplémentaires.
Logarithme est indiqué par log ou lg. Dans votre cas, je suppose que L'interprétation correcte est N + m * log (N).
EDIT: la base du logarithme n'a pas d'importance lors de l'analyse de la complexité asymptotique.