Cadeia infinita de grande

12

Primeiro, deixe-me escrever a definição de grande apenas para tornar as coisas explícitas.O

0 f ( n ) c g ( n ) , n n 0f(n)O(g(n))c,n0>0 tal que0f(n)cg(n),nn0

Digamos que temos um número finito de funções: satisftying:f1,f2,fn

O(f1)O(f2)O(fn)

Pela transitividade de , temos o seguinte:O ( f 1 ) O ( f n )OO(f1)O(fn)

Isso vale se tivermos uma cadeia infinita de ? Em outras palavras, ?O ( f 1 ) O ( f )OsO(f1)O(f)

Estou tendo problemas para imaginar o que está acontecendo.

saadtaame
fonte

Respostas:

15

Primeiro precisamos esclarecer o que queremos dizer com "isso vale se tivermos uma cadeia infinita?". Nós a interpretamos como uma sequência infinita de funções tal forma que, para todos os , temos . Essa sequência pode não ter uma última função.i f i ( n ) = O ( f i + 1 ( n ) ){fi:NN1i}ifi(n)=O(fi+1(n))

Podemos observar o limite das funções na sequência, ou seja, . No entanto, é possível que o limite não exista. E mesmo que exista, talvez não tenhamos . Por exemplo, considere a sequência de funções . Para cada , e, portanto, . No entanto, portanto, .f 1 ( n ) = O ( f ( n ) ) f i ( n ) = Nf(n)=limifi(n)f1(n)=O(f(n)) ifi(n)=Θ(n)fi(n)=O(fi+1(n))f(n)=limifi(n)=0=Θ(1)f1(n)O(f(fi(n)=niifi(n)=Θ(n)fi(n)=O(fi+1(n))f(n)=limifi(n)=0=Θ(1)f1(n)O(f(n))

Por outro lado, podemos observar o limite da sequência das classes que não precisa ser igual à classe do limite das funções . Temos , portanto e para todos os . O limite superior contém todos os elementos (funções neste caso) que ocorrem infinitamente com freqüência e o limite inferior contém todos os elementos que ocorrem em todos para algunsO ( f i ) O ( f i + 1 ) f jlim i O ( f i ) = lim sup i O ( f i ) = lim inf i O ( f i ) = n NfiO(fi+1)O(fi)O(fi+1)j O ( f i ) , i n 0 n 0fjlimiO(fi)=lim supiO(fi)=lim infiO(fi)=nNk>nO(fk)jO(fi),in0n0 (que pode depender do elemento). Como a sequência de classes é monotonicamente crescente, ambas existem e são iguais. Isso justifica o uso de .lim

frafl
fonte
3
Existem duas séries: uma de funções (que pode convergir ou não) e uma de conjuntos (onde cada conjunto é um superconjunto do anterior; é por isso que essa série converge - veja a definição de lim inf e lim sup para conjuntos) . A primeira parte responde à pergunta sem a parte , a segunda parte responde a parte negativamente (se for algum tipo de limão). f f fff
frafl
E se o número de termos for incontável? :)
SamM 5/13
Usando algumas instruções bem-ordenadas ou você deseja substituir a série por algo mais contínuo? :)
frafl
@ Kaveh Muito obrigado, faz muito sentido agora. Se você pudesse justificar o uso de limites e o que essa coisa de lim significa, então isso completará meu entendimento.
Saadtaame
1
@ saadtaame: Talvez seja porque a pergunta acima ainda não pergunta o que você quer saber? Se bem me lembro, você adicionou por causa de um comentário sugerido. Se você fornecer algum contexto, talvez alguém possa reformular a pergunta novamente. f
frafl
5

Sim, é possível ter uma cadeia infinita.

Tenho certeza de que você já conhece alguns exemplos: Você tem uma cadeia infinita aqui: polinômios de grau crescente. Você pode ir mais longe? Certo! Um exponencial cresce mais rápido (assintoticamente falando) do que qualquer polinômio. E, é claro, você pode continuar:S ( x ) S ( x 2 ) ... S ( x 42 ) ... S ( e x ) O ( E x ) O ( x

O(x)O(x2)O(x42)
O(x)O(x2)O(x42)O(ex)
O(ex)O(xex)O(e2x)O(eex)

Você também pode construir uma cadeia infinita na outra direção. Se então (aderindo a funções positivas, pois aqui discutimos as assintóticas das funções de complexidade). Então, temos por exemplo:f=O(g)1g=O(1f)

O(x)O(x2)O(exx2)O(exx)O(ex)

De fato, dada qualquer cadeia de funções , você pode criar uma função que cresça mais rapidamente do que todas elas. (Suponho que são funções de a .) Primeiro, comece com a idéia . Isso pode não funcionar porque o conjunto pode ser ilimitado. Mas, como estamos interessados ​​apenas em crescimento assintótico, basta começar pequeno e crescer progressivamente. Leve o máximo a um número finito de funções. f1,,fnffiNR+f(x)=max{fn(x)nN}{fn(x)nN}

f(x)=max{fn(x)1nN}if Nx<N+1
Em seguida, para qualquer , , pois . Se você deseja uma função que cresça estritamente mais rápida ( ), .NfNO(f)xN,f(x)fN(x)f=o(f)f(x)=x(1+f(x))
Gilles 'SO- parar de ser mau'
fonte
Todas essas respostas (a sua e a outra) se baseiam no pressuposto de que sabemos o que acontece no infinito, eles não são satisfatórios para mim, não sei sobre o OP (por que não devemos ter um grupo fechado com tamanho infinito) ?)
4
@SaeedAmiri Sinto muito, não entendo o seu comentário: o que você quer dizer com “sabemos o que acontece no infinito, eles não são satisfatórios para mim”?
Gilles 'SO- stop be evil'