Qual é a definição "correta" de limites superior e inferior?

19

Seja f(n) o pior caso de tempo de execução de um problema na entrada de tamanho n . Vamos tornar o problema um pouco estranho, fixando f(n)=n2 para n=2k mas f(n)=n para n=2k+1 .

  1. Então, qual é o limite inferior do problema? A maneira como eu entendi é apenas o limite inferior de f(n) . Mas sabemos que f(n)=Ω(n2) implica que existe constante k , n0 tal que para todos n>n0 , f(n)>kn2 , o que não é verdade. Assim, parece que só podemos dizer f(n)=Ω(n). Mas normalmente, chamaremos o problema de um limite inferior de Ω(n2) , certo?

  2. Supondo que g(n)=Ω(n2) , o que significa que existe constante k , n0 tal que para todos n>n0 , g(n)>kn2 . Vamos supor também que um problema tenha tempo de execução g(n) . Se pudermos reduzir esse problema para todos os números primos n para outro problema (com o mesmo tamanho de entrada), podemos dizer que o tempo de execução do outro problema tem um limite inferior de Ω(n2) ?

Wei Yu
fonte
12
É por isso que os matemáticos usam lim sup e lim inf.
Peter Shor
11
Então eu acho que entendo a diferença. Acho que as pessoas que postam entenderão o Omega infinitamente. Mas, caso eu queira fazer uma distinção explícita, existem outras anotações que eu possa usar além de expandi-la?
Wei Yu
3
kg(n)kn2lim infg(n)
lim supg(n)n2k
kg(n)kn2g(n)kn2n
lim infg(n)n2k
g(n)kn2n
 
12
@ Wei: Para a maioria dos teóricos da complexidade (veja Lance abaixo), sua função é θ (n ^ 2); para a maioria dos algoritmos (consulte Knuth ou CLRS), sua função é Ο (n ^ 2) e Ω (n). Ambas as notações são quase, mas não completamente, padrão em suas subcomunidades; para piorar as coisas, essas duas subcomunidades se sobrepõem fortemente! Portanto, se importa qual notação você usa, você deve dizer explicitamente qual notação você está usando. (Felizmente, isso raramente importa.)
Jeffε
2
@Jeffe. Eu acredito que você deve postar seu comentário como resposta.
22411 chazisop

Respostas:

13

A definição correta def(n)=Ω(n2) é que existe algum tal que para infinitamente muitos n , f ( n ) k n 2 . A definição infinitamente frequente de limites inferiores lida com seus problemas e é como os usamos na prática.k>0nf(n)kn2

Fiz um post sobre isso em 2005.

Alguns livros escolares acertam essa definição, outros não.

Lance Fortnow
fonte
14
Knuth discorda de você: portal.acm.org/citation.cfm?id=1008329
Jeffε
4
O CLRS e a Wikipedia também não concordam com você. A definição infinitamente frequente é uma alternativa digna de nota, mas parece ser menos utilizada.
Anónimo
Eu acho que essas definições todos concordam quando o conjunto de exceções é medida 0.
Carter Tazio Schonwald
2
f(n)=Ω(n2) f(n)=o(n+1)Ωo
András Salamon
2
oOooOn=Ω(f(n))f(n)=Ω(n2)nΩ(n2)Ω
András Salamon 27/03
4

f(n)Ω(n)

Ω(f(n))={gδ>0:n0>0:n>n0:g(n)δf(n)}.

f(n)Ω(n2)

Marcus Ritt
fonte
2

Não sei qual é o mais amplamente usado, mas acredito que conheço o uso mais antigo (de qualquer maneira para a ciência da computação).

No artigo de 1965 de Hartmanis & Stearns "Sobre a complexidade computacional dos algoritmos", o Corollary 2.1 é:

UTinfnT(n)U(n)0SUST

SKO(K(n))T(n)n/kknT(n)T(n+1)

k=1

O corolário 2.2 é o inverso do descrito acima e usa o limite supremo, mas ainda possui esses requisitos. Eu acho que, à medida que os algoritmos se tornaram mais complexos com o passar dos anos, é possível que os requisitos tenham sido relaxados.

chazisop
fonte
2

Eu acho que devemos distinguir entre duas coisas:

  • um limite inferior para uma função
  • um limite inferior para um problema (algoritmo)

Para funções, quando fixamos uma ordem, a definição de limite inferior / superior segue a mesma. Se a relação de ordem for majoração assintótica (ignorando fatores constantes)

fg:c,nm>n. f(x)cg(x)

OΩ

Time(t(n))n2n2o(t(n))

Kaveh
fonte