Notação de Landau

Todas as cinco classes do sistema Landau descrevem o comportamento assiptótico, ou seja, o comportamento quando o tamanho do problema tende ao infinito. Embora isso possa parecer irrelevante para nossos – muito finitos – problemas do mundo real, a experiência mostrou que o comportamento dos algoritmos do mundo real reflete esse comportamento infinito bem o suficiente em dados reais para ser de uso prático.

Grande O #

A notação Big O fornece limites superiores para o crescimento de funções. Intuitivamente para f ∊ O(g), f cresce no máximo tão rápido quanto g.

Formalmente f ∊ O(g) se e somente se existe um número positivo C e um número positivo ``n tal que para todos os números positivos m > n temos

C⋅g(m) > f(m).

Intuição desta definição #

Intuição sobre C #

C é responsável pela deglutição de fatores constantes nas funções. Se h é duas vezes f, ainda temos h ∊ O(g) já que C pode ser duas vezes maior. Para isso, existem duas razões:

• Notação mais fácil: f ∊ O(n) é preferível a f ∊ O(7.39 n).
• Abstração: Quaisquer unidades de tempo são engolidas nessas considerações porque não há nada a ganhar com elas; eles diferem entre as máquinas e os algoritmos podem ser avaliados sem isso. Como C engole fatores constantes, as classes de complexidade permanecem as mesmas mesmo em uma máquina dez vezes mais rápida.

Intuição sobre n #

n é responsável pelas turbulências iniciais da deglutição. Um algoritmo pode ter uma sobrecarga de inicialização enorme para pequenas entradas, mas compensa a longo prazo. A escolha de n permite entradas suficientemente grandes para obter o foco enquanto o trecho inicial é ignorado.

Intuição sobre m #

m abrange todos os valores maiores que n - para formalizar a ideia “de n em diante, isso vale”.