Quel est le sens de O( polylog(n) )? En particulier, comment est polylog(n) définie?

Résumé:

Lorsque universitaire (informatique) des documents de dire "O(polylog(n))", que signifient-ils? Je ne suis pas confus par le "Big-Oh" de notation, dont je suis très familier avec, mais plutôt par la fonction polylog(n). Ils ne parlons pas de l'analyse complexe de la fonction Lis(Z) je pense. Ou sont-ils? Quelque chose de totalement différent, peut-être?

Plus de détails:

Surtout par intérêt personnel, j'ai été récemment à la recherche sur les divers documents de Comprimé Suffixe Tableaux, par exemple Avantages de l'Arrière de la Recherche -- Efficace de la Mémoire Secondaire et Distribué de la mise en Œuvre de Comprimé Suffixe Tableaux. La complexité de calcul des estimations dit parfois impliquer polylog(n), qui est une fonction que je ne suis pas familier avec.

Wikipedia donne une définition de la polylogues(z) qui semble principalement sur l'analyse complexe et la théorie analytique des nombres. Mon soupçon est que ce n'est pas lié à la polylog(n) dans la compression de documents, bien que j'aimerais entendre le contraire de quelqu'un de plus compétent. Si c'est le cas, pourquoi est-il exactement de la pensée raisonnable pour omettre l'indice?

Mon seul autre supposition est que peut-être O(polylog(n)) est censé signifier "Asymptotique d'une fonction polynomiale de log(n)." Mais c'est seulement une supposition: je n'ai aucune preuve de cela, et ce serait un abus de notation pour démarrer.

Dans tous les cas, un lien vers un raisonnablement définition infaillible serait grandement apprécié!

  • Dans le rapport résumé, il est dit "... le CSA peut être recherché en O(m) temps à chaque fois = O(polylog(n))."
  • Oh, peut-être Sadakane [SOUDE 2002] a votre réponse définitive.
InformationsquelleAutor Managu | 2009-11-26
  1. 69

    Abus de notation ou pas, polylog(n) signifie "certains polynomial en log(n)", tout comme "la poly(n)" peut signifier "certains polynôme en n". Donc O(polylog(n)) signifie "O((log n)k) pour un certain k". (Voir Wikipédia: Polylogarithmic, ou, à voir les choses dans leur contexte, le prof, Scott Aaronson du blog: Mon Préféré Taux De Croissance.)

    Le point est que, tout comme nous, souvent, ne se soucient pas des facteurs constants, il est souvent commode d'ignorer les pouvoirs de logarithmes. Parfois, le "journal des facteurs" sont ignorées entièrement et vous pouvez voir "∏(f(n))" — O avec un tilde au-dessus d'elle — qui moyens "O(f(n) polylog(f(n)))", c'est à dire, "O(f(n) (log f(n))k) pour un certain k".

    • Juste assez. Merci pour les liens!
    • it is often convenient to ignore powers of logarithms Étrange. Comment peut ignorer les pouvoirs de logarithmes être pratique, quand il change de sens en tout?
    • De la même manière, il est souvent commode d'ignorer des facteurs constants, même si elle change de sens — là, tout dépend de ce que vous voulez vous concentrer sur. Tout polylogarithmic fonction se développe plus lentement que O(n^ε) pour tous ε. Ainsi, lorsque que vous vous souciez est l'exposant n — par exemple, en tentant de distinguer entre les n^2.1 et n^2 — ces polylogue facteurs n'a pas d'importance. O(n^2 polylog(n)) est O(n^(2+ε)) pour tout ε, alors nous écrire ∏ (n^2).
    • J'ai trouvé votre réponse vraiment utile dans la compréhension de la Master Théorème de résolution des récurrences
    • Donc, il devrait probablement être écrit comme O(poly(log n)), et puis c'est clair! O(polylog(n)) est source de confusion.
    • Oui c'est peut-être contribué. Dans ce cas, le mot "polylogarithmic" était déjà en usage avant de les O() notation s'est répandue, de sorte que "polylogue" est une abréviation pour "polylogarithmic", plutôt que d'être composé à partir de zéro à partir de la notation comme "poly(journal)" (qui comme vous le dites aurait été plus clair).

    InformationsquelleAutor ShreevatsaR
  2. 2

    La manière dont il est utilisé dans ce document semble être décrit quelque chose comme:

    O(log^p n)

    InformationsquelleAutor Hamish Smith
  3. 1

    Polylog(n) est juste "polynôme dans le journal de n". Wikipédia

    InformationsquelleAutor Donnie
  4. 1

    Différents polylogue article. Vous êtes à la conjecture est assez proche.

    InformationsquelleAutor Kevin Montrose
  5. 0

    Je suis sûr qu'ils signifient seulement le nombre entier positif axe réel: Re(n) = n

    InformationsquelleAutor kolypto
  6. 0

    Wolfram vous donne un sélection, dont la polylogarithmes page vous semble la plus prometteuse.

    InformationsquelleAutor Ewan Todd