Complexidade Assintótica

Determinar a função exata do tempo de execução de um programa pode ser uma tarefa complexa - é mais simples determinar a ordem do tempo de execução. É uma definição mais útil, porque para valores grandes de n (sendo n o tamanho da entrada), apenas a ordem de crescimento é relevante. O comportamento assintótico da função é o limite que f(n) atinge quando n aumenta.
Considerações:

• constantes aditivas e multiplicativas não são importantes: podem ser desprezadas
• um polinômio de grau k é O(n^k)
• o termo de maior ordem da função é que conta

Existem 3 notações utilizadas para expressar o comportamento de funções assintóticas:

• Notação O (O grande) - é o limite assintótico superior da ordem de crescimento da função de custo do algoritmo.
  Definição: uma função f(n) é O(g(n)) se existem duas constantes c, n0 >= 0 tais que 0 <= f(n) <= c·g(n) para todo n >= n0.
  Significado: c·g(n) é um limite superior de f(n) para valores grandes de n

---


• Notação Θ - é o limite assintótico firme ou justo ou restrito da ordem de crescimento da função de custo.
  Definição: Uma função f(n) é Θ g(n)) se é  Ω g(n)) e O(g(n)), isto é, se existem constantes c1, c2, n0 > 0 tais que 0 <= c1 g(n) <=  f(n) <= c2g(n) para todo n >= n0Significado: f(n) e g(n) tem a mesma ordem de crescimento. Θ indica um limite firme.

---

• Notação Ω - é o limite assintótico inferior da ordem de crescimento da função de custo.
  Definição: Uma função f(n) é Ω g(n)) se existem constantes positivas c, n0 tais que f(n) >= c·g(n) para n >= n0
  Significado: c·g(n) é um limite inferior de f(n) para n grande.

Existem ainda as notações o (o pequeno) e w (menos utilizadas).
Uma função f(n) é o(g(n)) se, para qualquer constante c > 0 existe uma constante n0 > 0 tal que f(n) < c g(n) para todo n >= n0 (limite superior não assintoticamente restrito). Uma função f(n) é w(g(n)) se, para qualquer constante c > 0 existe uma constante n0 > 0 tal que c g(n) < f(n) para todo n >= n0 (limite inferior não assintoticamente restrito).

Propriedades e características:
O, Θ, Ω são transitivas e reflexivas
● f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n))
● f(n) = O(f(n))
Θ é simétrica
● f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n))
f(n) = O(g(n)) se e somente se g(n) = Ω(f(n))
analogia com 2 números reais a e b
● f(n) = O(g(n)) » a <= b
● f(n) = o(g(n)) » a < b
● f(n) = Ω(g(n)) » a >= b
● f(n) = Ω(g(n)) » a > b

● f(n) = Θ(g(n)) » a = b

Uma expressão pode ser igualada a uma notação, mas o contrário não acontece.

Classes de complexidade (comportamento assintótico especificado pela notação O)

• complexidade constante: f(n) é O(1)
• complexidade logarítmica: f(n) é O(log n)
• complexidade linear: f(n) é O(n)
• complexidade linear logarítmica: f(n) é O(nlog n)
• complexidade quadrática: f(n) é O(n²)
• complexidade cúbica: f(n) é O(n³)
• complexidade exponencial: f(n) é O(2ⁿ)

Algoritmos com complexidade exponencial normalmente são relacionados a problemas intratáveis. Um algoritmo é considerado intratável se não existe um algoritmo polinomial [O(p(n)) em que p(n) é um polinômio] para resolvê-lo. Portanto, algoritmos polinomiais normalmente são uma boa solução para o problema.