A notação O

Entenda a notação O (Big O notation) e porquê ela é tão importante na análise de complexidade de algoritmos

A notação O ou Big O Notation é um tópico em ciência da computação muitas vezes considerado complicado e, em alguns casos, considerado irrelevante para o dia à dia de trabalho de desenvolvedores de software para o mercado. Mas será que é assim mesmo? Particularmente, considero uma das mais fundamentais ferramentas com a qual um programador pode avaliar um algoritmo/solução. Neste artigo, vamos compreender esse fundamento e como ele é uma métrica confiável, lógica e matemática sobre análise e comparação de algoritmos. 

Imagem de um plano cartesiano com várias curvas mostrando como diferentes tipos de complexidades de execução de algoritmos se comportam assintoticamente.

Introdução

Quando se fala de análise e complexidade de algoritmos estamos na verdade falando de comportamento assintótico de funções. Mas o que é isso? Bem, de forma simplória seria observar a curva de uma função e tentar classificá-la de modo a pode afirmar: ah, essa função nunca será maior do que esta outra. No caso dos programas de computadores estamos tentando classificar um algoritmo de modo a dizer que ele nunca será pior do uma classe inteira de algoritmos conhecidos. Tenho um artigo inteiramente dedicado ao comportamento assintótico de funções, caso você queira entender melhor esta parte. Neste artigo, vamos seguir pela perspectiva da Ciência da Computação.

A notação O foi originalmente postulada em 1894 por um matemático alemão chamado Paul Bachmann. Em 1976 Donald Knuth escreve uma carta à SIGACT propondo que os editores de periódicos e artigos adotem a notação O como forma de análise de algoritmos em suas publicações.

Vamos começar nosso estudo através de um exemplo hipotético. Considere que você quer avaliar dois algoritmos para envio de arquivos na Internet. Vamos chamá-los de algoritmo A e B. Vamos assumir em nosso exemplo que A tem complexidade em O(n²) e B em O(n). Não se preocupe, nós ainda entraremos no tópico complexidade e o que o "O" significa. Vamos ver então em um gráfico o crescimento dessas funções que representam a complexidade de nossos algoritmos:

Gráfico mostrando o crescimento das duas funções A e B. A função A na ordem de N ao quadrado e a função B na ordem de N. Na imagem é possível notar que A está acima de B.

Na figura acima podemos notar algumas coisas. Considere que no eixo x temos o tamanho do arquivo em gigabytes. Esse arquivo é o parâmetro de entrada de nossos algoritmos. Já no eixo y temos o número de operações necessárias para fazer o envio deste arquivo. Logo, podemos notar então que: à medida que tamanho do arquivo aumenta, o algoritmo A explode exponencialmente em número de operações. Este algoritmo segue uma classe, uma ordem de funções que se comportam/crescem como uma exponencial quadrática. Já o algoritmo B demonstra um crescimento linear, pois à medida que o tamanho do arquivo de entrada cresce, o numero de operações cresce na mesma proporção. Ou seja, linearmente.

Outra coisa essencial a se notar neste exemplo é a marcação em vermelho no ponto (1,1). Observe que, se alguém utilizar e comparar estes programas utilizando sempre arquivos menores do que 1 Gb, o algoritmo A será considerado mais eficiente, pois executa menos operações, segundo este gráfico. Esse detalhe é importante pois isto é fundamental para a análise do comportamento assintótico das funções que representam a execução destes algoritmos. 

Este foi um exemplo hipotético com objetivo de demonstrar a intuição por trás da notação O e sua aplicabilidade para comparar algoritmos. Vamos aprofundar!

A notação O (Big O notation)

Quando um algoritmo tem complexidade O(n) dizemos que ele é na "Ordem de n" ou simplesmente "Ó de n". A notação O é referente ao limite superior de uma função. Ou seja, existe uma função à qual o algoritmo estudado nunca terá um ponto acima da curva desta função. Por isso dizemos ela é limitada superiormente. Vamos entender isso.


int upload_file (char *file_name, int file_size) {
  ...
  for(int i = 0; i < file_size; i++) {

    // do some operation
  }
  ...
}

A bloco de código acima é um exemplo de algoritmo que executa alguma operação n vezes.  Considere n o parâmetro file_size. Como este programa faz um loop cujo tamanho depende de n, ele cresce linearmente em função de n. Neste sentido, podemos afirmar que este algoritmo nunca terá um crescimento assintótico superior a O(n). Ou seja, ele é limitado superiormente por O(n). Ele tem um crescimento linear. Dito isto, vamos definir a notação O:

f(n)=O(g(n)),se existirem uma constante c e um valor n0 tal que0≤f(n)≤c×g(n),∀n≥n0

Podemos ler da seguinte forma: A função f(n) cresce no máximo na ordem de g(n) para qualquer valor da entrada n que seja maior ou igual a n0. Ou seja, g(n) é um limite superior para o crescimento de f(n). Utiliza-se uma constante c positiva de modo a poder deslocar a função g(n) e mesmo assim ela ser um limite superior de f(n) para todos os valores maiores do que n0. Essa constante é mais clara quando se estuda a notação big Θ (letra grega Theta). O gráfico abaixo exemplifica visualmente o que a definição acima postula:

No gráfico nota-se que a partir de um valor n0 no eixo x, a função f de n está sempre abaixo da função g de n.

Em resumo: f(x) não cresce mais rápido do que g(n).

A medida de tempo: Operações

O que exatamente é o eixo y quando analisamos o comportamento das funções que representam os algoritmos? Estamos falando de operações. Operações como uma soma, um if dentro de um programa são consideradas operações constantes. É muito comum ver essa definição sendo chamada de O(1). No entanto, quando estamos falando de instruções de máquina olhamos o número de ciclos de CPU para execução uma determinada operação. Então um if, uma soma, ou carregar um dado da memória principal, cada uma dessas operações pode ter custo diferente em cada processador em que é executado. 

Assim, por mais que às vezes, uma dessas operações pode custar 5 ciclos e outra 1 ciclo, todas elas são consideradas constantes. Logo, ditas O(1). Mas não tem problema dizer O(5).

No entanto, se eu escrevo um for loop de n repetições, sendo n=10, independente do corpo do loop o programa irá executar n vezes. Logo, O(n). O que é importante notar? Independente da entrada n do programa, uma operação constante será sempre constante mas um loop por exemplo sempre irá crescer em função do tamanho dessa entrada. Ou seja, linearmente à n. A imagem abaixo mostra essas duas complexidades:

Uma linha horizontal representando uma operação constante e outra que cresce linearmente em função da entrada n representada na forma de uma reta diagonal.

Incrementalmente, vamos olhar um programa com dois loops aninhados e interpretar a complexidade inerente a este algoritmo e como esta interpretação seguirá a interpretação do exemplo anterior e como ela demonstra a intuição por trás da análise de complexidade.


int some_function (int n) {
  ...
  for(int i = 0; i < n; i++) {

    for(int j = 0; j < n; j++) {
      
      // do some operation
    }
  }
  ...
}

Este algoritmo está diretamente limitado à entrada n. Temos dois loops. Para cada iteração i do loop externo são executadas outras n iterações j. Ou seja, Se n for 8, temos que esse programa irá rodar n vezes n iterações. 8 vezes o loop externo, vezes 8 do loop interno, totalizando 64 iterações. 

No entanto, n é uma variável de entrada. E se n for 1 milhão? Ou se ele for 2, ou 6 bilhões? Como estimar o tempo de execução total deste programa? É aí que a Notação O nos ajuda a definir o crescimento de uma função que representa um algoritmo independente de qual o tamanho da entrada do programa. Tomando como exemplo o algoritmo apresentado acima temos:

n×n=n2Como a notação O é o limite superior,podemos afirmar para este exemplo que,no pior caso, este algoritmo irá crescer na ordem de n2Vamos chamar nosso programa de f(x),∴f(x)=O(n2)

Assim, seguindo esta intuição você poderá analisar a complexidade de diversos algoritmos para inferir como o tempo de execução dos programas se comportará em função do tamanho de suas entradas. 

Uma função ou algoritmo cheio de condicionais e regras que controlam sua execução pode retornar (chamar o return da função) antes executar por exemplo todas as iterações um loop. Ou seja, nem sempre um programa irá recair na complexidade do seu pior caso (limite superior). Mas é exatamente isto que a Notação O nos entrega, a estimativa do limite superior, o que pode inclusive ser o pior caso da execução de um algoritmo. Logo, podemos dizer que a execução daquele algoritmo nunca será pior do que a complexidade extraída pela Notação O. 

Mas e se você quiser não o limite superior mas sim o limite inferior? Ou quem sabe ambos? A respostas para estas perguntas estão em outros artigos neste blog. Um dedicado à Notação big Ω (letra grega ômega) para limite inferior e outro à Notação big Θ (letra grega Theta) para ambos limites.  

Se estamos falando de quantidade de operações, porquê dizemos complexidade de tempo de execução? Bem, quando falamos que uma operação é na verdade computada em ciclos de CPU dependendo do processador subjacente, na prática, estamos falando de tempo. Ciclos de CPU são medidos em nanosegundos. Logo, uma medida de tempo. 

Complexidade de Espaço

 Utiliza-se a mesma Notação O para descrever quanto armazenamento, tipicamente em memória, um algoritmo irá utilizar. Ou seja, se um programa precisa para cada elemento da entrada n, armazenar um dado na memória sem removê-lo até o fim de sua execução, se a entrada n for pequena é possível que este programa consiga executar. Mas e se o computador tiver 8 Gigabytes de memória RAM e a entrada do programa for um arquivo de 1 Terabyte, será que este programa que tem complexidade de espaço em O(n) é eficiente? A resposta é obviamente não.

Desta forma, quando falamos em complexidade de espaço (storage) estamos apenas mudando o eixo y de nossa análise. Ao invés de olharmos para uma medida de tempo estamos olhando para uma medida de espaço/armazenamento. Se na análise de tempo o problema é o programa demorar muito para executar ou nunca terminar, na análise de espaço o problema é não gerenciar bem a alocação ou liberação de memória de modo a não exaurir a máquina.   

Complexidades de algoritmos

Vamos ver um pequeno resumo de algumas complexidades comuns e simples na forma de um espectro ao qual quanto mais alto, pior é considerada a complexidade de tempo de execução. De forma oposta, quanto mais abaixo no espectro mais eficiente é o algoritmo:

Espectro mostrando de baixo para cima as complexidades consideras mais eficientes indo até o topo do espectro com as complexidades mais ineficientes. Neste exemplo, de O de 1 até O de n fatorial.

Um bom lugar para ver uma grande quantidade de complexidades conhecidas é o site Big O Cheat Sheet. Apesar desse grande compilado de complexidades o fundamento mais importante é conseguir analisar e inferir a complexidade olhando o código de um programa ou o algoritmo em estudo. Esse é o grande ferramental que a Notação O dá à Ciência da Computação.

Conclusão

Neste artigo compreendemos de onde vem o estudo da Notação O aplicada à computação na análise de complexidade de algoritmos. Baseado em uma intuição de como funções que representam nossos algoritmos crescem (comportamento assintótico), pudemos entender como analisar um programa em inferir seu comportamento.

Vimos qual a definição formal utilizada como métrica para dizer que um algoritmo é mais eficiente do que outro. Entendemos a relação de limites superiores e como, quando estamos falando de Notação O, podemos inferir o desempenho de um determinado algoritmo.

Se este tópico lhe interessou, você pode aprofundar o estudo lendo outros artigos que escrevi que fazem parte deste mesmo tópico em Ciência da computação. Você pode ler sobre a Notação Ômega, a Notação Theta e sobre Comportamento assintótico de funções. Como exercício para esta leitura tente pegar alguma função ou algoritmo que você esteja trabalhando e tente extrair a complexidade de tempo e espaço. Por fim, fique com esta imagem retirada do site Big O Cheat Sheet citado anteriormente para que você possa ver um comparativo de estrutura de dados conhecidas e suas complexidades por operação:

Uma tabela mostrando à esquerda o nome de várias estruturas de dados e à direita várias colunas com suas operações como inserção, busca, deleção. Dentro da tabela temos as complexidades destas operações para cada estrutura de dados.
Gustavo Pantuza
Gustavo Pantuza

Posts em português para fortalecer a comunidade brasileira de Ciência da computação. Caso tenha dúvidas, críticas ou sugestões de temas ou para o blog deixe nos comentários :)