Grande-O
Origem: Wikipédia, a enciclopédia livre.
A notação do Grande-O (ou como é conhecido em inglês, Big-O Notation, ou Big Omicron Notation) é uma notação matemática utilizada para analisar o comportamento assintótico de funções. Essa notação é bastante utilizada para a análise de algoritmos em ciência da computação.
A criação dessa notação é creditada ao matemático alemão Paul Bachmann, em 1894, na publicação da segunda versão da sua obra Analytische Zahlentheorie, sendo popularizada por outro alemão, Edmund Landau, e por causa disso, essa notação é também conhecida como "Símbolo de Landau". Essa notação é padronizada como "ordem de".
Índice |
[editar] Definição
Sejam duas funções reais f(x) e g(x). É definido:
A definição acima diz que a função f(x) é superiormante limitada pela função g(x).
Na definição foi utilizado f(x) = O(g(x)), mas é mais correto escrever f(x) é O(g(x)), ou f(x) ∈ O(g(x)), já que O(g(x)) define um conjunto de funções (ou classes de funções).
Para demonstrar que f(x) é O(g(x)), basta encontrar dois números (c e x0) tal que a definição acima seja satisfeita.
[editar] Exemplos
- A função f(x) = 10x + 11 é O(x). Para demonstrar, basta utilizar c = 11 e x0 = 10.
- A função f(x) = x2 + 100 é O(x2). Para demonstrar, basta utilizar c = 2 e x0 = 10.
[editar] Ordens mais comuns
Abaixo há uma lista de classes de funções que são bastante utilizadas para análise de algoritmos, por ordem crescente de crescimento de funções (as funções que têm um crscimento mais lento, são as primeiras). A letra c denota uma constante qualquer.
| notação | nome |
|---|---|
| O(1) | ordem constante |
| O(log x) | ordem logarítmica |
| O([log x]c) | ordem poli-logarítmica |
| O(x) | ordem linear |
| O(x · log x) | ordem linear-logarítmica |
| O(x²) | ordem quadrática |
| O(x³) | ordem cúbica |
| O(xc) | ordem polinomial |
| O(cx) | ordem exponencial |
| O(x!) | ordem fatorial |
| O(xx) | ordem exponencial |
[editar] Propriedades
[editar] Soma
Ex.: 
.
[editar] Produto
[editar] Multiplicação por uma constante
, desde que k≠0
