Variações do infinito Omega e Omega

7

Alguns autores definem de uma maneira um pouco diferente: vamos usar (leia “omega infinito”) para esta definição alternativa. Dizemos que se existe uma constante positiva tal que para infinitamente muitos números inteiros , enquanto o usual exige que isso valha para todos os números inteiros maiores que um certo . $\Omega$ $\overset{\infty}{\Omega}$ $f(n) = \overset{\infty}{\Omega}(g(n))$ $c$ $f(n) \geq c\cdot g(n) \geq 0$ $n$ $\Omega$ $n_0$

Mostram que para quaisquer duas funções e , que são assintoticamente não negativo, quer ou ou ambos, enquanto isso não é verdade se usarmos no lugar de . $f(n)$ $g(n)$ $f(n) = O(g(n))$ $f(n)= \overset{\infty}{\Omega}(g(n))$ $\Omega$ $\overset{\infty}{\Omega}$

Eu estou tentando aprender algoritmos. Mas eu sou incapaz de provar isso. Os especialistas podem me ajudar?

asymptotics landau-notation gopal
fonte

Tente usar as definições, tendo em mente que, para cada propriedade , vale para infinitos inteiros ou não para quase todos os números inteiros. Observe que é a negação do .

P

$P$

P

$P$

P

$P$

Ω^{\infty}

$\Omega^\infty$

O

$O$

Shaull

Veja aqui ou aqui .

Raphael

5

Dica: Se e é assintoticamente não-negativo, então para todos constantes positivas , para grande o suficiente . Isso segue ignorando a condição e negando a definição de . De fato, dessa maneira você obtém o resultado mais forte de que ou (mas não ambos). $f(n) \notin \overset{\infty}{\Omega}(g(n))$ $g(n)$ $c$ $f(n) \leq c \cdot g(n)$ $n$ $c \cdot g(n) \geq 0$ $f(n) \in \overset{\infty}{\Omega}(g(n))$ $f(n) \in \overset{\infty}{\Omega}(g(n))$ $f(n) \in o(g(n))$

Dica adicional: você pode começar mostrando que a negação de " para infinitamente muitos " é " para grande o suficiente ". $P(n)$ $n$ $\lnot P(n)$ $n$

Yuval Filmus
fonte

Não consigo entender a diferença de infinitamente muitos e para n grandes o suficiente . você conhece uma fonte que pode me ajudar?

Fatemeh Karimi

2

Sugiro uma boa base na teoria dos conjuntos e na lógica formal. Alguma coisa vale para todo grande o suficiente se existir , de forma que seja válida para todos . Ele vale para infinitos se o conjunto de para o qual ele é mantido é infinito.

n

$n$

n_{0}

$n_0$

n \geq n_{0}

$n\geq n_0$

n

$n$

n

$n$

Yuval Filmus

0

Eu posso dar um exemplo para que você possa entender melhor . Imagine uma pilha binomial. A operação de inserção é , mas é ? $\overset{\infty}{\Omega}(g(n))$ $O(logN)$ ${\Omega}(logN)$

Nos casos em que tivermos classificações em árvore de 4-3-2-1-0 e a inserção de uma árvore com classificação 0, será uma operação . Mas inserir uma árvore com classificação 0 no heap resultante da operação anterior (heap com classificação de árvore 5) será uma operação , pois apenas ponteiros devem ser adicionados e nenhum trabalho de mesclagem extra é necessário. ${\Omega}(logN)$ $O(1)$

Essa é a diferença essencial entre e . Por exemplo, a operação de inserção de heap binomial é para o conjunto de . Ele não afirma que quando a complexidade é mas para um conjunto infinito de n, mas não para todos ${\Omega}$ $\overset{\infty}{\Omega}$ $\overset{\infty}{\Omega}(logN)$ $n = \{{1,3,7,...,2^k - 1}\}$ $n \geq n_0$ ${\Omega}(logN)$ $n \geq n_0$

denis631
fonte

@YuvalFilmus por favor me corrija se eu estiver errado

denis631

Variações do infinito Omega e Omega

Respostas: