O que significa til, na notação big-O?

Estou lendo um artigo, e ele diz na descrição da complexidade do tempo que a complexidade do tempo é . $\tilde{O}(2^{2n})$

Pesquisei na Internet e na Wikipedia, mas não consigo encontrar o que esse til significa na notação big-O / Landau. No próprio artigo, também não encontrei nenhuma pista sobre isso. O que significa ? $\tilde{O}(\cdot)$

landau-notation Johannes Schaub - litb
fonte

"Eu pesquisei na internet" Como?!? :-) Normalmente, para perguntas como essa, minha primeira reação é que o Google dirá a resposta imediatamente. Mas para este, não tenho idéia de qual termo de pesquisa eu usaria!

David Richerby

Procurei "símbolos do landau til", mas nada conclusivo apareceu. Eu acho que o Google precisa de algum AI que sabe como um til aparência visual e procurar que no prestados TeX fotos: p

Johannes Schaub - litb

Outra que você vê às vezes é a estrela Big Oh, ou seja, . É comumente usado com, por exemplo, algoritmos de tempo exponencial exato, e a notação suprime fatores polinomialmente limitados no tamanho da entrada.

O^{*}

$O^*$

Juho

É uma variante do big-O que "ignora" fatores logarítmicos:

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

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

é 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)$

Da Wikipedia :

Essencialmente, é uma notação grande , ignorando fatores logarítmicos, porque os efeitos da taxa de crescimento de alguma outra função super-logarítmica indicam uma explosão na taxa de crescimento para parâmetros de entrada de tamanho grande que é mais importante para prever um desempenho ruim em tempo de execução do que o efeitos de ponto mais fino contribuídos pelo (s) fator (es) de crescimento logarítmico. Essa notação é frequentemente usada para obviar o “nitpicking” dentro das taxas de crescimento que são declaradas muito restritas para os assuntos em questão (uma vez que é sempre para qualquer constante e qualquer ). $O$ $\log^k n$ $o(n^\varepsilon)$ $k$ $\varepsilon > 0$

manlio
fonte

Estou certo ao concluir que e são diferentes? Isso é confuso porque eles parecem ser usados de forma intercambiável.

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

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

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

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

Johannes Schaub - litb 08/09

@ JohannesSchaub-litb Sim, existem funções que crescem mais que para cada ainda assim crescem menos que e, portanto, são incluídas no primeiro, mas não no segundo. Enfim: o objetivo dessa notação é mostrar apenas a parte importante da complexidade assintótica e geralmente não é considerado importante.

\log^{k} n

$\log^k n$

k

$k$

n

$n$

o (n)

$o(n)$

Bakuriu 8/09/16

Como corolário, é o mesmo que . @ JohannesSchaub-litb é o mesmo que . Caso você realmente queira dizer , isso inclui , mas também algumas funções crescendo um pouco mais rapidamente. As pessoas costumam usá-lo em vez de porque não está errado, é uma notação menos conhecida e a perda de precisão geralmente não importa.

\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$

Emil Jeřábek 8/09/16

Ah eu entendo agora, obrigado. Isso faz muito sentido

Johannes Schaub - litb 8/16

O que significa til, na notação big-O?

Respostas: