Qual é a diferença entre limite inferior e limite estreito?

99

Com a referência desta resposta , o que é Theta (limite rígido)?

Omega é o limite inferior, bastante conhecido, o tempo mínimo que um algoritmo pode levar. E sabemos que Big-O é para limite superior, significa o tempo máximo que um algoritmo pode levar. Mas não tenho ideia sobre o Theta.

Adeel Ansari
fonte

Respostas:

154

Big O é o limite superior, enquanto Omega é o limite inferior. Theta requer tanto Big O quanto Omega, então é por isso que é chamado de limite restrito (deve ser o limite superior e o inferior).

Por exemplo, um algoritmo que Omega(n log n)leva pelo menos n log ntempo, mas não tem limite superior. Uma tomada de algoritmo Theta(n log n)é muito preferencial, pois leva pelo menos n log n (Omega n log n) e não mais que n log n (Big O n log n).

Chris Bunch
fonte
7
Oh .. Agora, o termo "limite apertado" parece bastante auto-explicativo para mim. Obrigado Chris. Estúpido de mim, talvez estivesse esperando alguma ideia complexa. :)
Adeel Ansari
6
Sim, há um monte de notações extravagantes lançadas, mas não são muito complexas uma vez que você as entende.
Chris Bunch
4
Este documento disponível gratuitamente da Virginia Tech explica com exemplos as diferenças de desempenho entre algoritmos de diferentes complexidades e explica resumidamente a Análise Assintótica: people.cs.vt.edu/shaffer/Book/C++3e20120102.pdf
Alan
O que você quer dizer com "Um algoritmo tomando Theta (n log n) é muito preferencial, pois leva pelo menos n log n (Omega n log n) e não mais do que n log n (Big O n log n).", Como in, é a complexidade exata de um algoritmo como você escreveu, disse pelo menos Omega (nlogn) e no máximo BigO (nlogn)?
Nikhil Verma
1
Em termos simples, podemos chamar: limite superior (Grande (O)) como o pior caso? limite apertado como o caso médio? limite inferior (Omega) como o melhor caso?
Revanth
113

Θ notação (theta notação) é chamado tight-bound porque é mais preciso do que a notação O e Ω-notação (omega notação).

Se eu fosse preguiçoso, poderia dizer que a pesquisa binária em uma matriz classificada é O (n 2 ), O (n 3 ) e O (2 n ), e estaria tecnicamente correto em todos os casos. Isso ocorre porque a notação O especifica apenas um limite superior , e a pesquisa binária é limitada no lado superior por todas essas funções, mas não muito de perto. Essas estimativas preguiçosas seriam inúteis .

A notação Θ resolve este problema combinando a notação O e a notação Ω. Se eu disser que a pesquisa binária é Θ (log n), isso fornece informações mais precisas. Ele informa que o algoritmo é limitado em ambos os lados pela função fornecida, portanto, nunca será significativamente mais rápido ou mais lento do que o declarado.

Bill the Lizard
fonte
11
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every case- Parece que a maioria das pessoas no mundo dos computadores são preguiçosas apenas porque todo mundo fala principalmente sobre as complexidades do Big O apenas.
RBT
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every caseNo caso de alguém ser confundido com isto: Para esse tipo de funções que não são assintoticamente rígidas, a notação small-o é usada. Exemplo: - O limite 2n ^ 2 = O (n ^ 2) é assintoticamente rígido, mas o limite 2n = O (n ^ 2) não é. Leia mais: stackoverflow.com/questions/1364444/…
Dragos Strugar
18

Se você tem algo que é O (f (n)), significa que há k , g (n) tais que f (n)kg (n) .

Se você tem algo que é Ω (f (n)), isso significa que há k , g (n) tais que f (n)kg (n) .

E se você tem algo com O (f (n)) e Ω (f (n)) , então é Θ (f (n) .

O artigo da Wikipedia é decente, embora um pouco denso.

Charlie Martin
fonte
Agora lendo a família de notações de Bachmann-Landau. Obrigado Charlie, eu já fui lá antes, mas voltei sem prosseguir.
Adeel Ansari
Ei, é bom atualizar as composições de doutorado de vez em quando.
Charlie Martin
Observe que a notação big-O de Landau não se limita à complexidade algorítmica.
Charlie Martin de
Isso parece errado. Na primeira linha, deve ler-se "Se você tiver algo que seja O (g (n))", ou seja, em gvez de f, e o resto pode ser deixado como está. O mesmo vale para a segunda linha: deve ser "Se você tiver algo que é Ω (g (n))". Você pode, por favor, verificar?
Fabio diz Restabelecer Monica
O tópico todo está tão confuso que alguém com esse crédito também pode errar: D Brincadeiras à parte, alguém precisa corrigir essa resposta. Isso confunde as pessoas (me fez muito bem).
Rad
5

O limite superior assintótico significa que um determinado algoritmo é executado durante o período máximo de tempo, dependendo do número de entradas.

Vamos pegar um algoritmo de classificação como exemplo. Se todos os elementos de uma matriz estiverem em ordem decrescente, para classificá-los, levará um tempo de execução de O(n), mostrando a complexidade do limite superior. Se a matriz já estiver classificada, o valor será O(1).

Geralmente, O-notationé usado para a complexidade do limite superior.


O limite assintoticamente estreito (c 1 g (n) ≤ f (n) ≤ c 2 g (n)) mostra a complexidade do limite médio para uma função, tendo um valor entre os limites do limite (limite superior e limite inferior), onde c 1 e c 2 são constantes.

Sameenu
fonte
1
se a matriz for classificada, o limite ainda será O (n)
Arun Aravind
2
@ArunAravind Você pode explicar por quê?
novembro
3

As frases tempo mínimo e tempo máximo são um pouco enganosas aqui. Quando falamos sobre notações grandes O, não é o tempo real que nos interessa, mas como o tempo aumenta quando nosso tamanho de entrada fica maior. E geralmente é o tempo médio ou pior caso que estamos falando, não o melhor caso , que geralmente não é significativo para resolver nossos problemas.

Usando a pesquisa de array na resposta aceita para a outra questão como exemplo. O tempo que leva para encontrar um número específico na lista de tamanho n é n / 2 * alguma_constante em média. Se você tratá-lo como uma função f(n) = n/2*some_constant, ele não aumentará mais rápido do que g(n) = n, no sentido dado por Charlie. Além disso, não aumenta mais lentamente do que g(n)qualquer um. Portanto, g(n)é na verdade um limite superior e um limite inferior de f(n)na notação Big-O, então a complexidade da pesquisa linear é exatamente n , o que significa que é Theta (n).

A este respeito, a explicação na resposta aceita para a outra pergunta não é totalmente correta, que afirma que O (n) é o limite superior porque o algoritmo pode ser executado em tempo constante para algumas entradas (este é o melhor caso que mencionei acima, que não é realmente o que queremos saber sobre o tempo de execução).

PolyThinker
fonte
Então, podemos dizer que Ω é o melhor caso e O é o pior? . .. e devemos substituir os termos como melhor caso e pior caso, respectivamente?
Adeel Ansari
O melhor caso é O (1) para algum problema?
Zach Langley
1
@Adeel, no, Theta e O podem se referir tanto ao caso médio quanto ao pior caso. @Zach, bem, não exatamente. Obrigado por apontar isso.
PolyThinker
0

Se eu fosse preguiçoso, poderia dizer que a pesquisa binária em uma matriz classificada é O (n2), O (n3) e O (2n), e estaria tecnicamente correto em todos os casos.

Podemos usar a notação o ("little-oh") para denotar um limite superior que não é assintoticamente restrito. Ambos big-oh e little-oh são semelhantes. Mas, big-oh provavelmente é usado para definir o limite superior assintoticamente restrito.

Finn está faltando
fonte
0

Precisamente o limite inferior ou $ \ omega $ bfon f (n) significa o conjunto de funções que são assintoticamente menores ou iguais af (n) ou seja, U g (n) ≤ cf (n) $ \ para todos $ `un≥ n 'Para algum c, n' $ \ in $ $ \ Bbb {N} $

E o limite superior ou $ \ mathit {O} $ em f (n) significa o conjunto de funções que são assintoticamente maiores ou iguais af (n) que matematicamente diz,

$ g (n) \ ge cf (n) \ para todos os n \ ge n '$, para algum c, n' $ \ em $ $ \ Bbb {N} $.

Agora o $ \ Theta $ é a intersecção dos dois escritos acima

$\theta $

Como se um algoritmo fosse "exatamente $ \ Omega \ left (f (n) \ right $", então é melhor dizer que é $ \ Theta \ left (f (n) \ right) $.

Ou podemos dizer também que nos dá a velocidade real onde $ \omega $nos dá o limite mais baixo.

PI Gogole
fonte
-2

A diferença básica entre

Bloco de citação

Limite superior assintoticamente e limite assintoticamente estreito Asym.upperbound significa um determinado algoritmo que pode ser executado com a quantidade máxima de tempo dependendo do número de entradas, por exemplo, na classificação algo se todos os elementos da matriz (n) estão em ordem decrescente, então para ascendê-los levará um tempo de execução de O (n) que mostra a complexidade do limite superior, mas se eles já estiverem classificados, então, levará ohm (1). Portanto, geralmente usamos a notação "O" para a complexidade do limite superior.

Asym. limite estreito mostra o por exemplo (c1g (n) <= f (n) <= c2g (n)) mostra o limite estreito de modo que a função tenha o valor entre dois limites (limite superior e limite inferior), dando o caso médio.

BOBBY Z
fonte
2
Você não deve responder a perguntas antigas se sua resposta não adicionar nada às respostas já aceitas.
alestanis