Signification de lg * N dans l'analyse algorithmique

Je suis en train de lire à propos de l'algorithmique analyse et j'ai lu qu'un certain algorithme (pondéré rapide de l'union avec le chemin de compression) est d'ordre N + M lg * N. Apparemment si c'est linéaire, car lg * N est une constante dans cet univers. Quelle opération mathématique qui est mentionné ici. Je suis pas familier avec la notation lg * N.

source d'informationauteur themaestro

  1. 27

    Les réponses apportées jusqu'ici sont faux. lg* n (lire "journal d'étoiles") est le logarithme itéré. Elle est définie comme une manière récursive comme

             0             if n <= 1
lg* n =
         1 + lg*(lg n) if n > 1

    Une autre façon de penser, il est le nombre de fois que vous avez l'itération logarithme avant que le résultat est inférieur ou égal à 1.

    Il pousse très lentement. Vous pouvez en lire plus sur Wikipedia qui comprend quelques exemples d'algorithmes pour qui lg* n apparaît dans l'analyse.

  2. 0

    Je suppose que vous parlez 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 entièrement littérale.
    lg*N ne semblent augmenter avec N comme par leur table sur le côté droit de la diapositive; il arrive juste à croître à un rythme lent qu'il ne peut pas être considéré comme 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 sont la définition de "lg*N" 2^(lg*(N-1)). Ce qui signifie qu'une valeur de N de 2^(2^(65536)) [un nombre bien plus grand] donnerait lg*N = 6, par exemple.

  3. 0

    La définition récursive de lg*n par Jason est équivalent à
    lg*n = m lorsque 2 II m <= n < 2 II de (m+1)
    où

    2 II m = 2^2^...^2 (répété exponentiation, m des copies de 2)

    est Knuth double flèche vers le haut de la notation. 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.

    Donc lg*n=4 pour 2^{16} <= n < 2^{65536}.
    La fonction lg*n approche de l'infini extrêmement lentement.
    (Plus rapide que l'inverse de la fonction d'Ackermann A(n,n) qui implique n-2 flèches vers le bas.)

    Stephen

  4. -3

    lg est "LOG" ou à l'inverse de la fonction exponentielle. lg se réfère généralement à la base 2, mais algorithmique pour l'analyse, la base généralement n'importe pas.

  5. -3

    lg n désigne le journal de la base de n. C'est la réponse à l'équation 2^x = n. Dans Big O l'analyse de la complexité, de la base de journal n'est pas pertinent. Des puissances de 2 cultures dans les CS, il n'est donc pas une surprise si nous avons à choisir une base, il sera la base 2.

    Un bon exemple de cas où elle est soulevée est pleinement un arbre binaire de hauteur h, qui a 2^h-1 nœuds. Si nous soit n le nombre de nœuds de cette relation est l'arbre est à la hauteur de lg n avec n nœuds. L'algorithme de la traversée de cet arbre prend au plus lg n pour voir si une valeur est stockée dans l'arbre.

    Comme attendu, le wiki a beaucoup plus d'infos.

  6. -3

    Logarithme est dénoté par le journal 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 quand on fait de l'analyse de la complexité asymptotique.