Grande-O

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Mergefrom 2.svg
O artigo ou secção Notação Big-O deverá ser fundido aqui. (desde junho de 2012)
(por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Cheque ambas (1, 2) e não esqueça de levar toda a discussão quando levar o caso para a central.).

A notação do Grande-O ou notação assintótica (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".

De um modo informal, dizemos que uma função f pode ser representada como O(g(x)) se ambas funções, para x suficientemente grande, "crescem" da mesma forma, ou seja, são "proporcionais". Se f é O(g(x)), então, para x grande o suficiente, se num dado intervalo f dobra, então g "dobra" também (com erro pequeno), e vice-versa. Por exemplo, f(x) = 10x^5 + 3x^3 é O(x^5).

Definição[editar | editar código-fonte]

Sejam duas funções reais f(x) e g(x). É definido:

O(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existem } c,x_0 \mbox{ constantes positivas tais que} \\ \forall x:x_0\le x: 0\le f(x)\le cg(x) \end{matrix}\right\}

A definição acima diz que a função f(x) é superiormente 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)), não basta encontrar dois números c e x0 tais que a definição acima seja satisfeita, já que podem existir funções que satisfaçam a condição referida apenas para alguns valores. As demonstrações são usualmente feitas por indução.

Exemplos[editar | editar código-fonte]

  • A função f(x) = 10x + 11 é O(x). Como exemplo, basta utilizar c = 12 e x0 = 10.
  • A função f(x) = x2 + 100 é O(x2). Como exemplo, basta utilizar c = 2 e x0 = 10.

Ordens mais comuns[editar | editar código-fonte]

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 crescimento mais lento, são as primeiras). A letra c denota uma constante qualquer.

notação nome
O(1) ordem constante
O(log n) ordem logarítmica
O([log n]c) ordem poli-logarítmica
O(n) ordem linear
O(n · log n) ordem linear-logarítmica
O(n²) ordem quadrática
O(n³) ordem cúbica
O(nc) ordem polinomial
O(cn) ordem exponencial
O(n!) ordem fatorial
O(nn) ordem exponencial

Propriedades[editar | editar código-fonte]

Soma[editar | editar código-fonte]

O(f(n)) + O(g(n)) = O(\max \lbrace f(n),g(n) \rbrace)

Ex.: f(n) = 10 \log n + 5 (\log n)^3 + 7n + 3n^2 + 6n^3 \in \hbox{O}(n^3).

Produto[editar | editar código-fonte]

O(f(n))O(g(n)) = O(f(n)g(n))

Multiplicação por uma constante[editar | editar código-fonte]

O(k g(n)) = O(g(n)), desde que k≠0