Conceitos de Programação: Big O Notation

February 7th, 2008 § 8 comments

Este é o terceiro artigo em uma série sobre conceitos de programação. O primeiro falava sobre Lazy Evaluation e como simular isso em uma linguagem sem suporte nativo ao conceito de uma forma simples mas funcional. O segundo falava sobre Tail Recursion e como aproveitar isso em linguagens que implementam a característica.

Antes de começar o artigo, um aviso: o tratamento que eu estou dando aos assuntos aqui é informativo, com a intenção de incentivar os leitores que desconhecem ou querem aprender sobre o assunto em questão a procurar mais sobre o assunto. Como tal, podem existir erros nos mesmos, derivados da minha própria incompreensão de alguns pontos. Nesse caso, como sempre, a parte de comentários está aberta. Aceito tanto sugestões como correções. Isso vale para todo e qualquer artigo da série. Dito isso, podemos continuar.

Neste terceiro artigo, vamos falar um pouco sobre Big O Notation, ou Notação O, que, em teoria da computação é usada para descrever como o tamanho da entrada fornecido a um algoritmo qualquer afeta os recursos que o mesmo utiliza, sejam estes de memória ou tempo de execução.

Conhecer esse tipo de informação sobre um algoritmo é a base de qualquer otimização que possa ser feita sobre o mesmo. Não só para entender como o mesmo opera em termos de eficiência geral mas também para decidir corretamente quando for necessário sacrificar alguma aspecto de performance ou complexidade em favor de outro. Isso vale tanto para uso de CPU, memória como para rede, disco e qualquer outro recurso similar.

A Notação O, na verdade, é uma classe inteira de notações. Nesse artigo vamos cobrir somente uma parte no que tange à análise de complexidade de um algoritmo.

Complexidade versus performance

Antes de prosseguirmos, uma distinção deve ser feita aqui.

Performance é uma medida de quanto dos recursos disponíveis um algoritmo usa. Isso depende tanto do código quanto da máquina onde o mesmo está rodando.

Complexidade, por outro lado, é como o algoritmo escala, ou seja, o que acontece quando mais e mais dados são passados ao mesmo? Complexidade afeta performance, obviamente, mas o converso não é verdadeiro.

Sendo assim, a Notação O descreve a complexidade do algoritmo e não sua performance. Isso será visto mais adiante com um exemplo.

Entendendo a notação

Como mencionado acima, o principal objetivo da notação O, no que tange à descrição de complexidade de um algoritmo é explicar de maneira sucinta como o tamanho do problema afeta o número de operação necessárias para executar o mesmo. Operações podem ser atribuições, comparações, cálculos númericos, leituras, escritas, e assim por diante, tomadas em unidade.

A notação não descreve o número exato de operações, mas está interessada em casos específicos de operação. Em outras palavras, ela é igualmente válida para descrever o melhor caso, o pior caso, ou o caso médio de um algoritmo qualquer.

Para um dado problema, podemos ter as seguintes situações comuns:

Constante: O(1), ou ordem 1
Isso significa que o uso de recursos é constante seja qual for o tamanho da entrada. Obviamente, esse é o melhor nível de complexidade possível.
Linear: O(n), ou ordem n
Isso significa que o uso de recursos é proporcional ao tamanho da entrada.
Logarítmico: O(log n), ou ordem logaritmo n
Isso significa que o uso de recursos varia em proporção logarítmico ao tamanho da entrada.
Quadrático: O(n2), ou ordem n ao quadrado
Isso significa que o uso de recursos varia em proporção exponencial ao tamanho da entrada.

Para colocar isso em contexto, alguns exemplos:

  • Determinar se um número é par ou ímpar é O(1)
  • Encontrar um item em uma lista ordenada por busca binária é O(log n)
  • Resolver o problema do caixeiro viajante por força bruta é O(n!)

A importância da escolha

Para entender a importância da escolha correta de implementação, podemos usar um exemplo concreto:

O famoso Quicksort, em seu caso típico é O(n log n). Em seu pior caso, O(n2). Isso para tempo de execução. É claro que isso depende de uma implementação correta do mesmo, mas em qualquer implementação correta, essa é a complexidade.

Em termos de uso de memória, porém, para um implementação correta é sempre O(n log n), a menos que a execução seja in-place, caso qual o uso de memória é O(1). Em outras palavras, uma mudança de implementação aqui, mesmo correta, pode ter uma impacto enorme em um dos recursos usados pelo algoritmo.

O caso converso também é verdadeira para a escolha. Há momentos em que você deve saber balancear as expectativas. Se você descobre que o seu algoritmo é O(n3) e que existe uma forma de transformá-lo em O(n2) mas que isso vai tomar um ano e tornar o código incompreensível, não faz muito sentido ganhar com a redução por maior que ela aparentemente seja.

Digo aparentemente, porque você pode descobrir que para o tamanho de sua entrada, a complexidade não faz diferença. Se o seu conjunto de entrada é distribuído demais para que o algoritmo caia no melhor caso, faz sentido explorar o pior caso, por exemplo.

O que não é trivial

Obviamente, a equação que determinada a eficiência pode expressar qualquer relação. Entretanto, ela não usa constantes ou termos de ordem inferior porque para à medida que n aumenta, o impacto desses termos se torna insignificante. Para entender isso, considere o Bubblesort, um dos piores algoritmos possíveis para ordenação (quase um Bogosort):

A implementação trivial em Ruby é a seguinte:

def bubblesort(*items)
  loop do
    swapped = false
    for i in (0..items.size - 2)
      if items[i] > items[i + 1]
        items[i], items[i + 1] = items[i + 1], items[i]
        swapped = true
      end
    end
    break unless swapped
  end
  items
end

Essa implementação é O(n2). Você pode reparar que ela gasta n * (n + 1) passagens em média, ou seja, O(n2 + n), o que é o mesmo que dizer O(n2).

Agora, suponha que a implementação seja melhorada:

def bubblesort(*items)
  l = items.size - 1
  loop do
    swapped = false
    l -= 1
    for i in (0..l)
      if items[i] > items[i + 1]
        items[i], items[i + 1] = items[i + 1], items[i]
        swapped = true
      end
    end
    break unless swapped
  end
  items
end

Você verá que agora o algoritmo faz a metade das comparações, porque para antes de chegar aos números que já foram ordenadas. O número de operações agora é n + (n-1) + (n-2) + … + 1, que dá n(n + 1) / 2. Como demonstrado acima, entretanto, isso ainda é O(n2).

A razão é que a entrada ainda influencia exponencialmente a execução. Se você introduzir computar o número de computações feitas verá que esse número cresce exatamente da forma descrita na notação.

Com isso em mãos, uma forma rápida de descobrir quão bem um algoritmo escala é plotar a equação que determina sua complexidade. O crescimento do gráfico mostra isso de forma bem visual. A ordem é:

Determinando complexidade

A maneira de determinar complexidade é verificar quantas operações simples o algoritmo precisa fazer antes de terminar sua execução.

Tome os loops abaixo, por exemplo:

for i in (0..n)
end

for i in (0..m)
end

A complexidade do primeiro é O(n) e a do segundo é O(m). A de ambos é O(n + m), que é o mesmo que O(max(n, m)).

Veja agora o caso abaixo:

for i in (0..n)
  for j in (0..n)
  end
end

A complexidade agora é O(n * n), ou O(n2).

A maioria dos casos pode ser estimada igualmente, verificado as condições que limitam cada caso. Na pior das hipóteses, é possível instrumentar a função e depois lançar os resultados em um programa que gere um gráfico do resultado colhido. Veja o resultado do pior caso da ordenação descrita anteriormente:

Computações versus Itens

Conclusão

Saber estimar ou pelo menos procurar a complexidade de um algoritmo é fundamental para qualquer programador. Qualquer tipo de otimização mais pesada é irrelevante sem isso. O maior problema está no fato de que certas otimizações são contra-intuitivas como demonstrado acima. Entender as variações se torna, então, a necessidade mais premente para otimizar de maneira adequada.

Obviamente, em muitos casos, uma otimização simples pode ser suficiente para os propósitos do código. Mesmo assim, uma análise um pouco mais profunda pode render benefícios inesperados.

§ 8 Responses to Conceitos de Programação: Big O Notation"

  • Leandro says:

    O Bogosort é diferente do Bubblesort, e muito menos eficiente: ele escolhe dois elementos ao acaso, troca-os de lugar e verifica se a sequência está ordenada; repete até que esteja ordenada. É, tosco.

    Do contrário, gostei do artigo. Resumiu uns 30% da cadeira de análise de algorítmos que eu tive ano retrasado :)

  • Ronaldo says:

    Opa, corrigido! A entrada na Wikipedia está escrita de uma forma que dá a impressão que os dois são sinônimos em uma leitura mais rápida. Qualquer outra correção, pode mandar. :-)

    Obrigado também pelas palavras. Espero estar passando alguma coisa para o pessoal que está lendo e que ainda não está familiarizado com os termos e conceitos.

  • Elomar França says:

    Novamente, um ótimo artigo. E veio numa hora bem apropriada.

    Parei no tópico de Big O Notation do JEDI[http://www.dfjug.org/DFJUG/jedi/index.jsp] porque era díficil encontrar um texto sobre o assunto que fosse de fácil compreensão e não enchesse a tela de fórmulas imensas.

    [Pra se ter uma idéia dessa dificuldade, o segundo artigo no google sobre “Big O Notation” em português é “Solteiros interessados em Big O notation”. O primeiro é esse.]

    E que a série continue.

  • Aparente alguns gráficos estão quebrados no post.

  • Ronaldo says:

    Opa, Elomar! Obrigado. Bom saber que os artigos estão sendo bem-vindos. :-)

    Eu estava pensando escrever sobre isso desde antes da série porque é um assunto que muita gente desconhece mas que pode ajudar bastante em decisões, mesmo nas simples.

    Qualquer sugestão, estou ouvindo. 😛

    Opa, Osvaldo! Tudo bom? Há um gráfico só mas aparentemente está aparecendo corretamente. Não está mostrando no agregador ou no navegador?

  • Excelente artigo. Carece um pouco de exemplos de análise de algoritmos com complexidade logarítmicas mas está perfeito. Vc tem um grande dom didático. Continue assim. Apontarei este link no meu blog.

  • rafael says:

    Muito bom o artigo ! Estamos vendo isso na faculdade. Mas foi muito bem explicado, vc tem uma linguagem muito fácil.

    😉

  • Gabriel Amaral says:

    Realmente muito bom o artigo ! Está muito bem explicado, eu tive essa matéria na faculdade em 2006, mas acredito que entendi muito melhor com a sua explicação.

Leave a Reply

Your email address will not be published. Required fields are marked *

What's this?

You are currently reading Conceitos de Programação: Big O Notation at Superfície Reflexiva.

meta