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

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.

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).

Θ 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 ² ), O (n ³ ) e O (2 ⁿ ), 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.

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.

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 ₁ g (n) ≤ f (n) ≤ c ₂ 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 ₁ e c ₂ são constantes.

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).

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.

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.

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.