Qual é a diferença entre o limite inferior e apertada ligado?

Question

Com a referência deste , o que é Theta (tight bound)?

Omega é obrigado inferior, bem entendido, o tempo mínimo de um algoritmo pode demorar. E sabemos Big-O é para limite superior, significa que o tempo máximo de um algoritmo pode demorar. Mas eu não tenho nenhuma idéia sobre o Theta.

Answer 1

Big O é o limite superior, enquanto que Omega é o limite inferior. Theta requer tanto Big O e Omega, de modo que por isso que é referido como um apertado obrigado (deve ser tanto a limites superior e inferior).

Por exemplo, um algoritmo tomando Omega(n log n) leva pelo menos tempo n log n, mas não tem limite superior. Um Theta(n log n) algoritmo tomada é muito preferencial uma vez que leva pelo menos n log n (Omega n log n) e não mais do que n log n (Big O n log n).

Answer 2

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

Se eu fosse preguiçoso, eu poderia dizer que busca binária em um array ordenado é O (n ² ), O (n ³ ) e O (2 < sup> n ), e eu seria tecnicamente correta em cada caso. Isso porque a notação O especifica apenas um limite superior , e busca binária é delimitada no lado elevado por todas essas funções, mas não muito de perto. Estas estimativas preguiçosos seria inútil .

resolve T-notação esse problema por combinando O-notação e O-notação. Se eu disser que busca binária é T (log n), que lhe dá informações mais precisas. Diz-lhe que o algoritmo é delimitada ambos lados pela função dada, por isso nunca será significativamente mais rápido ou mais lento do que o indicado.

Answer 3

Se você tem algo que de O (f (n)) isso significa que há são k , g (n) tal que f (n) = kg (n) .

Se você tem algo que de O (f (n)) isso significa que há são k , g (n) tal que f (n) = kg (n) .

E se você tem um algo com O (f (n)) e O (f (n)) , então é < em> T (f (n) .

O href="http://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer"> artigo é decente, se um pouco denso.

Answer 4

assintótica limite superior fortes meios de que um determinado algoritmo executado durante o período máximo de tempo, dependendo do número de entradas.

Vamos dar uma algoritmo de classificação como um exemplo. Se todos os elementos de um array estão em ordem decrescente, em seguida, classificá-los, vai demorar um tempo de execução de O(n), mostrando a complexidade limite superior. Se a matriz já está classificado, o valor será O(1).

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

---

Assintoticamente apertado ligado (c ₁ g (n) = f (n) = c ₂ g (n)) mostra a média complexidade ligada por uma função, tendo um valor entre os limites encadernadas (limite superior e um limite inferior), em que c ₁ e C ₂ são constantes.

Answer 5

As frases tempo mínimo e tempo máximo são um pouco enganosa. Quando falamos de grandes notações O, não é o tempo real em que estamos interessados, é como o tempo aumenta quando o nosso tamanho da entrada fica maior. E é geralmente o tempo médio ou pior caso estamos a falar, não melhor dos casos , o que geralmente não é significativo em resolver os nossos problemas.

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

Neste sentido, a explicação na resposta aceita para a outra pergunta não é inteiramente correcto, que afirma que O (n) é limite superior porque o algoritmo pode ser executado em tempo constante para algumas entradas (esta é a melhor dos casos eu mencionei acima, que não é realmente o que queremos saber sobre o tempo de execução).

Answer 6

Se eu fosse preguiçoso, eu poderia dizer que busca binária em um array ordenado é O (n2), O (n3) e O (2n), e eu seria tecnicamente correto em cada caso.

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

Answer 7

Precisamente o limite inferior ou $ \ omega $ bfon f (n) significa o conjunto de funções que são assintoticamente menos ou igual a f (n) i L g (n) = cf (N) $ \ para todos $ `n un=' Para alguns c, n' $ \ em $ $ \ Bbb {N} $

E o limite superior ou $ \ mathit {O} $ em f (n) significa o conjunto de funções que são assintoticamente maior ou igual a f (n) que conta matematicamente,

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

Agora, o $ \ Theta $ é a interseção do acima escrito dois

$\theta $

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

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

Answer 8

A diferença básica entre

Blockquote

asymptotically limite superior e assintoticamente restrito Asym.upperbound significa um determinado algoritmo de que podem executado com valor máximo de tempo, dependendo do número de entradas, por exemplo, na separação algo se todos os elementos (n) da matriz são, por ordem decrescente, em seguida, para lhes ascendente vai demorar um tempo de execução de o (n), que mostra a complexidade limite superior, mas se eles já estão classificadas, então vai demorar ohm (1) .so que geralmente usado notação "o" para a complexidade limite superior.

Asym. tightbound mostra ligadas a por exemplo (C1G (n) <= f (n) <= C2G (n)) mostra o limite ligado apertado de modo a que a função de ter o valor de entre dois ligados (limite superior e limite inferior), dando o caso médio.