Qual é a diferença entre T (n) e O (n)?

Question

Às vezes eu vejo T (n) com o símbolo T estranho com algo no meio dela, e às vezes apenas O (n). É apenas preguiça de digitar porque ninguém sabe como escrever este símbolo, ou significa algo diferente?

Answer 1

Breve explicação:

Se um algoritmo é de T (g (n)), isso significa que o tempo de execução do algoritmo como n (tamanho de entrada) se torna maior é proporcional a g (n).

Se um algoritmo é de O (g (n)), isso significa que o tempo de execução do algoritmo como n fica maior é no máximo proporcional a g (n).

Normalmente, mesmo quando as pessoas falam sobre O (g (n)) eles realmente significam T (g (n)), mas tecnicamente, há uma diferença.

---

Mais tecnicamente:

o (n) representa o limite superior. T (n) meios apertado ligado. O (n) representa limite inferior.

f (x) = T (g (x)) sse f (x) = O (g (x)) e f (x) = O (g (x))

Basicamente, quando dizemos que um algoritmo é de O (n), é também O (n ² ), O (n ^1000000 ), O (2 ⁿ ), ... mas um (n) algoritmo T é não T (n ² ).

De facto, uma vez que ® ((n) g) meios de f (n) = para valores suficientemente grandes de N, f (n) pode ser ligada dentro de c ₁ g (n) e c ₂ g (n) para alguns valores de c ₁ e C ₂ , isto é, a taxa de crescimento de f é assintoticamente igual ag: g pode ser um limite inferior e e um limite superior de f. Isto implica directamente f pode ser um limite inferior e um limite superior de g bem. Consequentemente,

f (x) = T (g (x)) sse g (x) = T (f (x))

De modo semelhante, para mostrar a f (n) = T (g (n)), que é suficiente para mostrar g é um limite superior de f (isto é, f (n) = O (g (n))) e f é um limite inferior de g (ou seja, f (n) = O (g (n)), que é a mesma coisa que exacto g (n) = o (f (n))). Concisa,

f (x) = T (g (x)) sse f (x) = O (g (x)) e g (x) = O (f (x))

---

Há também pouca-oh e pouco omega (ω) notações representando solta limites superior e solta mais baixos de uma função.

Para resumir:

f(x) = O(g(x)) (big-oh) significa que a taxa de crescimento de f(x) é asymptotically menor ou igual para para a taxa de crescimento de g(x).

f(x) = Ω(g(x)) (big-omega) meios que a taxa de crescimento de f(x) é asymptotically maior ou igual a a taxa de crescimento de g(x)

f(x) = o(g(x)) meios (pequenos-oh) que a taxa de crescimento de f(x) é asymptotically menos de o taxa de crescimento de g(x).

f(x) = ω(g(x)) (little-omega) meios que a taxa de crescimento de f(x) é asymptotically maior o taxa de crescimento de g(x)

f(x) = Θ(g(x)) (teta) significa que a taxa de crescimento de f(x) é asymptotically igual a o taxa de crescimento de g(x)

Para uma discussão mais detalhada, você pode ler a definição na Wikipedia ou consultar um livro clássico como Introdução aos Algoritmos por Cormen et al.

Answer 2

Há uma maneira simples (um truque, eu acho) para lembrar que os meios de notação o.

Todas as notações Big-O pode ser considerada como tendo um bar.

Ao olhar para um O, o bar é na parte inferior, por isso é um (assintótica) limite inferior.

Ao olhar para um T, o bar é obviamente no meio. Por isso, é um (assintótica) apertado amarrado.

Quando caligrafia O, você costuma terminar no topo, e desenhar um rabisco. Por conseguinte, o (n) representa o limite superior da função. Para ser justo, este não funciona com a maioria das fontes, mas é a justificativa original dos nomes.

Answer 3

é Big "O"

é Big Theta

http://en.wikipedia.org/wiki/Big_O_notation

O grande significa que seu algoritmo será executado em não mais passos do que em determinada expressão (n ^ 2)

Big Omega significa que seu algoritmo será executado em não menos etapas do que na expressão dada (n ^ 2)

Quando ambos condição são verdadeiras para a mesma expressão, você pode usar a notação teta grande ....

Answer 4

Ao invés de fornecer uma definição teórica, que estão muito bem resumidos aqui já, vou dar um exemplo simples:

Suponha que o tempo de execução de f(i) é O(1). Abaixo está um fragmento de código cujo tempo de execução assintótica é Θ(n). É sempre chama os tempos f(...) função n. Tanto a parte inferior e o limite superior é n.

for(int i=0; i<n; i++){
    f(i);
}

O segundo fragmento de código abaixo tem o tempo de execução de assintótica O(n). Ele chama a função f(...) no máximo vezes n. O limite superior é n, mas o limite poderia ser Ω(1) ou Ω(log(n)), dependendo do que acontecer f2(i) dentro diminuir.

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}

Answer 5

Theta é uma forma abreviada de se referir a um situtation especial onde The Big O e Omega são os mesmos.

Assim, se um reivindicações The Theta is expression q, então eles são também, necessariamente, alegando que Big O is expression q e Omega is expression q.

---

áspero analogia:

Se: Teta reivindicações, "Aquele animal tem 5 pernas." segue-se que: Big O é verdade ( "Esse animal tem menor ou igual a 5 pés.") e Omega é verdade ( "Aquele animal tem mais de ou igual a 5 pés.")

É apenas uma analogia grosseira porque as expressões não são necessariamente números específicos, mas em vez funções de diferentes ordens de magnitude, como log (n), n, n ^ 2, (etc.).

Answer 6

A traçar poderia fazer as respostas anteriores mais fácil de entender:

T-Notação - mesma ordem | O-Notação - Limite superior

Em Inglês,

À esquerda, nota que há um limite superior e um limite inferior que são ambos da mesma ordem de grandeza (isto é, g (n) ). Ignorar as constantes, e se o limite superior e limite inferior têm a mesma ordem de grandeza, pode validamente dizer f (n) = T (g (n)) ou f (n) está em grande teta de g (n) .

A partir da direita, o exemplo mais simples, ele está dizendo que o limite superior g (n) é simplesmente a ordem de grandeza e ignora a constante c (assim como tudo grande O notação faz).

Answer 7

f(n) pertence a O(n) se existe k positiva como f(n)<=k*n

f(n) pertence a Θ(n) se existe k1 positivo, k2 como k1*n<=f(n)<=k2*n

artigo da Wikipedia sobre Big O Notation

Answer 8

Conclusão: nós consideramos grande O, grande ? e grande O como a mesma coisa.

Por quê? Vou dizer a razão abaixo:

Em primeiro lugar, vou esclarecer uma declaração errada, algumas pessoas pensam que só se preocupam o pior complexidade de tempo, por isso use sempre grande O lugar de grande ?. Eu vou dizer que este homem está sacaneando. Limite superior e inferior são usados ??para descrever uma função, não é usado para descrever o tempo de complexidade. A função do tempo tem o seu pior limites superior e inferior; a melhor função do tempo tem sua limites superior e inferior também.

A fim de explicar claramente a relação entre as grandes O e grande ?, vou explicar a relação entre as grandes O e pequena o primeiro. A partir da definição, podemos facilmente saber que pequeno o é um subconjunto de grande O. Por exemplo:

T (n) = n ^ 2 + n, podemos dizer T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Mas para os pequenos o, T (n) = O (n ^ 2) não atendem à definição de pequena o. Então, só T (n) = O (n ^ 3), T (n) = O (n ^ 4) estão correctos para o pequeno. A T redundantes (n) = O (n ^ 2) é o quê? É grande ?!

Geralmente, dizemos grande S é O (n ^ 2), dificilmente a dizer T (n) = O (n ^ 3), T (n) = O (n ^ 4). Por quê? Porque nós consideramos grande O tão grande ? inconscientemente.

Da mesma forma, nós também consideramos grande O tão grande ? inconscientemente.

Em uma palavra, ó grande, grande ? e grande O não são a mesma coisa a partir das definições, mas eles são a mesma coisa na nossa boca e cérebro.

Answer 9

Usando limites

Vamos considerar f(n) > 0 e g(n) > 0 para todos n. É ok para considerar isso, porque o algoritmo mais rápido real tem pelo menos uma operação e completa a sua execução após o início. Isto irá simplificar o cálculo, porque podemos usar o valor (f(n)) em vez do valor absoluto (|f(n)|).

1. f(n) = O(g(n))

   Geral:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞   g(n)
   

   Para g(n) = n:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞    n
   

   Exemplos:

       Expression               Value of the limit
   ------------------------------------------------
   n        = O(n)                      1
   1/2*n    = O(n)                     1/2
   2*n      = O(n)                      2
   n+log(n) = O(n)                      1
   n        = O(n*log(n))               0
   n        = O(n²)                     0
   n        = O(nⁿ)                     0
   

   Contra-exemplos:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ O(log(n))                 ∞
   1/2*n    ≠ O(sqrt(n))                ∞
   2*n      ≠ O(1)                      ∞
   n+log(n) ≠ O(log(n))                 ∞
   

2. f(n) = Θ(g(n))

   Geral:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞   g(n)
   

   Para g(n) = n:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞    n
   

   Exemplos:

       Expression               Value of the limit
   ------------------------------------------------
   n        = Θ(n)                      1
   1/2*n    = Θ(n)                     1/2
   2*n      = Θ(n)                      2
   n+log(n) = Θ(n)                      1
   

   Contra-exemplos:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ Θ(log(n))                 ∞
   1/2*n    ≠ Θ(sqrt(n))                ∞
   2*n      ≠ Θ(1)                      ∞
   n+log(n) ≠ Θ(log(n))                 ∞
   n        ≠ Θ(n*log(n))               0
   n        ≠ Θ(n²)                     0
   n        ≠ Θ(nⁿ)                     0