Que signifie ?

Que signifie ?$\log^{O(1)}n$

Je connais la notation big-O, mais cette notation n'a aucun sens pour moi. Je ne trouve rien non plus à ce sujet, car il n'y a aucun moyen qu'un moteur de recherche interprète cela correctement.

Pour un peu de contexte, la phrase où je l'ai trouvée se lit "[...] nous appelons une fonction [efficace] si elle utilise l' espace et tout au plus le temps par objet."$O(\log n)$$\log^{O(1)}n$

Vous devez ignorer un instant le fort sentiment que le " " est au mauvais endroit et continuer à travailler avec la définition malgré tout. f ( n ) = log O ( 1 ) n signifie qu'il existe des constantes k et n 0 telles que, pour tout n ≥ n 0 , f ( n ) ≤ log k ⋅ 1 n = log k n .$O$$f(n) = \log^{O(1)}n$$k$$n_0$$n\geq n_0$$f(n) \leq \log^{k\cdot 1}n = \log^k n$

Notez que signifie ( log n ) k . Les fonctions de la forme log O ( 1 ) n sont souvent appelées polylogarithmiques et vous pourriez entendre les gens dire: « f est polylog  n ».$\log^k n$$(\log n)^k$$\log^{O(1)}n$$f$$n$

Vous remarquerez qu'il est facile de prouver que , puisque 2 n ≤ k n pour tout n ≥ 0 , où k = 2 . Vous vous demandez peut-être si 2 log n = log O ( 1 ) n . La réponse est oui puisque, pour assez grand n , log n ≥ 2 , donc 2 log n ≤ log 2 n pour assez grand $2n=O(n)$$2n\leq k n$$n\geq 0$$k=2$$2\log n = \log^{O(1)}n$$n$$\log n\geq 2$$2\log n \leq \log^2n$ .$n$

Sur une note connexe, vous verrez souvent des polynômes écrits comme : même idée.$n^{O(1)}$

Il s'agit d'un abus de notation qui peut être interprété par la convention de l'espace réservé généralement acceptée : chaque fois que vous trouvez un terme Landau , remplacez-le (dans votre esprit ou sur le papier) par une fonction arbitraire g ∈ O ( f ) .$O(f)$$g \in O(f)$

Donc si vous trouvez

$\qquad f(n) = \log^{O(1)} n$

tu dois lire

pour certains g ∈ O ( 1 ) $\qquad f(n) = \log^{g(n)} n$$g \in O(1). \hspace{5cm} (1)$

Notez la différence de dire " à la puissance d'une constante": g = n ↦ 1 / n est une possibilité distincte.$\log$$g = n \mapsto 1/n$

Avertissement: L'auteur utilise peut-être encore plus d' abus de notation et souhaite que vous lisiez

pour certains g ∈ O ( 1 ) $\qquad f(n) \in O(\log^{g(n)} n)$$g \in O(1). \hspace{4.3cm} (2)$

Notez la différence entre (1) et (2); bien que cela fonctionne pour définir le même ensemble de fonctions à valeur positive ici, cela ne fonctionne pas toujours. Ne déplacez pas dans les expressions sans précaution!$O$

Cela signifie que la fonction croît au maximum sous forme de à la puissance d'une constante, c'est-à-dire log 2 ( n ) ou log 5 ( n ) ou log 99999 ( n ) ...$\log$$\log^2(n)$$\log^5(n)$$\log^{99999}(n)$

"Au plus " signifie qu'il existe une constante c telle que ce qui est mesuré est O ( log c n ) .$\log^{O(1)} n$$c$$O(\log^c n)$

Dans un contexte plus général, est équivalent à l'affirmation selon laquelle il existe des constantes a et b (éventuellement négatives) telles que f ( n ) ∈ O ( log a n ) et f ( n ) ∈ Ω ( log b n ) .$f(n) \in \log^{O(1)} n$$a$$b$$f(n) \in O(\log^a n)$$f(n) \in \Omega(\log^b n)$

Il est facile d'ignorer la borne inférieure de . Dans un contexte où cela importerait (ce qui serait très rare si vous êtes exclusivement intéressé par l'étude de la croissance asymptotique ), vous ne devriez pas avoir une confiance totale dans le fait que l'auteur signifie réellement la borne inférieure, et devrait se fier au contexte pour assure-toi.$\Omega(\log^b n)$

La signification littérale de la notation fait de l'arithmétique sur la famille de fonctions, résultant en la famille de toutes les fonctions log g ( n ) n , où g ( n ) ∈ O ( 1 ) . Cela fonctionne à peu près de la même manière que la multiplication de O ( g ( n ) ) par h ( n ) entraîne O ( g ( n ) h $\log^{O(1)} n$$\log^{g(n)} n$$g(n) \in O(1)$$O(g(n))$$h(n)$ , sauf que vous obtenez un résultat qui n'est pas exprimé si simplement.$O(g(n) h(n))$

Étant donné que les détails de la limite inférieure se trouvent probablement en territoire inconnu, il convient de regarder certains contre-exemples. Rappelons que tout est borné en magnitude ; qu'il existe une constante c telle que pour tout n suffisamment grand , | g ( n ) | < c .$g(n) \in O(1)$$c$$n$$|g(n)| < c$

En ce qui concerne la croissance asymptotique , seule la limite supérieure importante, car, par exemple, vous savez déjà que la fonction est positive. Cependant, en général, vous devez faire attention à la borne inférieure g ( n ) > - c .$g(n) < c$$g(n) > -c$

Cela signifie que, contrairement aux utilisations plus courantes de la notation big-oh, les fonctions qui diminuent trop rapidement peuvent ne pas être dans le ; par exemple, $\log^{O(1)} n$

$-1 \notin \log^{O(1)} n$