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) = n^2$ para $n=2k$ mas $f(n) = n$ para $n=2k+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) = \Omega(n^2)$ implica que existe constante $k$ , $n_0$ tal que para todos $n > n_0$ , $f(n) > kn^2$ , o que não é verdade. Assim, parece que só podemos dizer $f(n) = \Omega(n)$ . Mas normalmente, chamaremos o problema de um limite inferior de $\Omega(n^2)$ , certo?
Supondo que $g(n) = \Omega(n^2)$ , o que significa que existe constante $k$ , $n_0$ tal que para todos $n > n_0$ , $g(n) > kn^2$ . 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 $\Omega(n^2)$ ?

cc.complexity-theory time-complexity 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

lim sup \frac{g (n)}{n^{2}} \geq k

$\limsup \frac{g(n)}{n^2} \geq k$

k

$k$

g (n) \geq k n^{2}

$g(n) \geq k n^2$

lim inf \frac{g (n)}{n^{2}} \geq k

$\liminf \frac{g(n)}{n^2} \geq k$

g (n) \geq k n^{2}

$g(n) \geq k n^2$

n

$n$

$\$

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

13

A definição correta de $f(n)=\Omega(n^2)$ é que existe algum tal que para infinitamente muitos , . A definição infinitamente frequente de limites inferiores lida com seus problemas e é como os usamos na prática. $k>0$ $n$ $f(n)\geq kn^2$

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) = Ω (n^{2})

$f(n)=\Omega(n^2)$

f (n) = o (n + 1)

$f(n)=o(n+1)$

Ω

$\Omega$

o

$o$

András Salamon

2

o

$o$

O

$O$

o

$o$

o

$o$

O

$O$

n = Ω (f (n))

$n = \Omega(f(n))$

f (n) = Ω (n^{2})

$f(n) = \Omega(n^2)$

n \neq Ω (n^{2})

$n \ne \Omega(n^2)$

Ω

$\Omega$

András Salamon 27/03

4

$f(n)\in\Omega(n)$

Ω (f (n)) = {g ∣ \exists δ > 0 : \forall n_{0} > 0 : \exists n > n_{0} : g (n) \geq δ f (n)} .

$\Omega(f(n))=\{ g \mid \exists \delta>0:\forall n_0>0:\exists n>n_0: g(n)\geq \delta f(n)\}\textrm{.}$

$f(n)\in\Omega(n^2)$

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 é:

$U$ $T$ $\inf_{n \rightarrow \infty} \frac{T(n)}{U(n)} \geq 0$ $S_{U} \subseteq S_{T}$

$S_{K}$ $O( K(n) )$ $T(n) \geq n/k$ $k$ $n$ $T(n) \leq 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)

f ⪯ g : \exists c, n \forall m > n . f (x) \leq c g (x)

$f \preceq g : \exists c,n \forall m>n. \ f(x) \leq c g(x)$

$O$ $\Omega$

$\mathbf{Time}(t(n))$ $n^2$ $n^2$ $o(t(n))$

Kaveh
fonte

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

Respostas: