Que signifie tilde, en notation big-O?

Je lis un article, et il dit dans sa description de la complexité temporelle que la complexité temporelle est . $\tilde{O}(2^{2n})$

J'ai cherché sur Internet et wikipedia, mais je ne trouve pas ce que ce tilde signifie en notation big-O / Landau. Dans le journal lui-même, je n'ai trouvé aucun indice à ce sujet. Que signifie ? $\tilde{O}(\cdot)$

landau-notation Johannes Schaub - litb
la source

"J'ai cherché sur Internet" Comment?!? :-) Normalement, pour des questions comme celle-ci, ma première réaction est que Google vous donne immédiatement la réponse. Mais pour celui-ci, je n'ai aucune idée du terme de recherche que j'utiliserais!

David Richerby

J'ai cherché "landau symboles tilde" mais rien de concluant ne s'est présenté. Je suppose que Google a besoin d'une IA qui sait à quoi ressemble un tilde visuellement et recherche cela dans les photos TeX rendues: p

Johannes Schaub - litb

Un autre que vous voyez parfois est grande star Oh, qui est,

. Il est couramment utilisé avec, par exemple, des algorithmes de temps exponentiels exacts, et la notation supprime les facteurs liés polynomialement dans la taille d'entrée.

O^{*}

$O^*$

Juho

Réponses:

C'est une variante du big-O qui «ignore» les facteurs logarithmiques:

f (n) \in \tilde{O} (h (n))

$f(n) \in \tilde O(h(n))$

est équivalent à:

\exists k : f (n) \in O (h (n) \log^{k} (h (n)))

$\exists k : f(n) \in O \!\left( h(n)\log^k(h(n)) \right)$

De Wikipédia :

$O$ $\log^k n$ $o(n^\varepsilon)$ $k$ $\varepsilon > 0$

manlio
la source

O (2^{2 n} + o (n))

$O(2^{2n} + o(n))$

\tilde{O} (2^{2 n})

$\tilde{O}(2^{2n})$

\log^{k} n

$\log^k n$

k

$k$

n

$n$

o (n)

$o(n)$

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

O (2^{2 n} p o l y (n))

$O(2^{2n}\mathrm{poly}(n))$

O (2^{2 n} + o (n))

$O(2^{2n}+o(n))$

O (2^{2 n})

$O(2^{2n})$

O (2^{2 n + o (n)})

$O(2^{2n+o(n)})$

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

\tilde{O} (2^{2 n})

$\tilde O(2^{2n})$

\tilde{O}

$\tilde O$

Ah je comprends maintenant, merci. Cela a beaucoup de sens

Johannes Schaub - litb