¿Qué significa tilde, en notación big-O?

Estoy leyendo un papel, y dice en su descripción complejidad del tiempo que la complejidad es el tiempo . $\tilde{O}(2^{2n})$

He buscado en Internet y Wikipedia, pero no puedo encontrar lo que significa esta tilde en notación big-O / Landau. En el documento en sí tampoco he encontrado ninguna pista sobre esto. ¿Qué significa ? $\tilde{O}(\cdot)$

landau-notation Johannes Schaub - litb
fuente

"He buscado en internet" ¿Cómo? :-) Normalmente, para preguntas como esta, mi primera reacción es que Google le dirá la respuesta de inmediato. ¡Pero para este, no tengo idea de qué término de búsqueda usaría!

David Richerby

Busqué "tilda de símbolos de Landau" pero no apareció nada concluyente. Supongo que Google necesita un poco de inteligencia artificial que sepa cómo se ve visualmente una tilde y busque eso en imágenes de TeX renderizadas: p

Johannes Schaub - litb

Otro que a veces ves es la estrella de Big Oh, es decir,

. Se usa comúnmente con, por ejemplo, algoritmos de tiempo exponencial exacto, y la notación suprime factores polinómicamente delimitados en el tamaño de entrada.

O^{*}

$O^*$

Juho

Respuestas:

Es una variante del big-O que "ignora" los factores logarítmicos:

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

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

es equivalente a:

\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 Wikipedia :

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

manlio
fuente

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, ahora entiendo, gracias. Esto tiene mucho sentido

Johannes Schaub - litb