No post anterior, introduzimos o conceito de Análise Assintótica e falamos brevemente sobre o Big O Notation. Nesse post, vamos pincelar sobre como mensurar um algoritmo utilizando a notação.
Mas antes de mais nada é preciso reforçar: O Big O é apenas uma das métricas (número de passos proporcional ao tamanho do seu input) que pode te levar à conclusão de que o seu algoritmo é eficiente ou não. Em momento de implementação, outras métricas como memória, tempo, acesso a recursos e consumo de energia podem impactar nesse resultado.
Para tanto, é comum termos duas formas distintas de análise:
- Empírica: Tempo de execução do código, implementado na linguagem de programação de sua escolha.
- Analítica: Não leva em consideração o ambiente no qual o seu algoritmo irá executar, representando através de uma ordem de grandeza o tempo de execução do algoritmo.
Vamos focar no método analítico, claro. Se você está interessado no método empírico, ferramentas de profiling podem te dar ótimas dicas sobre a performance da sua solução.
Tempo x Espaço
É possível utilizar o Big O para medirmos quanto de espaço que um determinado algoritmo ocupa. Na Wikipedia existe inúmeros wikis sobre algoritmos famosos, e grande parte deles apresenta a seguinte estrutura:
Exemplo de card do Wikipedia mostrando os tempos de um algoritmo
O Merge sort, um dos mais famosos algoritmos de ordenação, além de ter uma performance média de O (n log n), em seu pior cenário ocupa O(n) de espaço. Onde n corresponde ao tamanho da entrada do algoritmo. Logo, se você passar um array de 10 posições para o Merge sort ordenar, ele ocupará outras 10 posições ao fim do processo.
Em contrapartida, o Bubble sort, também famoso mas nada performático (O(n2)), ocupa O(1) (não necessitando de novas posições na memória para fazer a ordenação).
Se você estiver projetando a sua solução para um ambiente limitado, será necessário levar em consideração o espaço, mas é muito comum nos tempos atuais sacrificarmos memória em prol do tempo de execução.
Quanto mais próximo de linear, melhor
Voltando o foco ao tempo de execução, é possível categorizarmos um bom algoritmo quando ele é o mais próximo possível de linear (se ele for sublinear ou constante, melhor ainda). Ou seja:
- Se ordernar 10 items leva 1 milissegundo;
- Ordenar 20 items deveria levar 2 milissegundos;
- E ordenar 100 items deveria levar 10 milissegundos.
Esse comportamento é linear, resultando em O(n). Mas o comportamento abaixo não é o dos melhores:
- Se ordenar 10 items leva 1 milissegundo;
- E ordenar 20 items leva 4 milissegundos;
- E ordenar 100 items leva 100 milissegundos;
- Temos uma progressão quadrática, resultando em O(n2).
Algo não tão desejável em se tratando de algoritmos.
Imagem via Phrasee.co
Mais um pouquinho de teoria
Vamos gastar um pouco de teoria aqui para definir Big O:
Se um tempo de execução é O(f(n)), então para um n suficientemente grande, o tempo de execução é no máximo k*f(n) para alguma constante k.
f(n) e Big O via pt.khanacademy.org
Dizemos que o tempo de execução é “big-O de f(n)” ou só “O de f(n)”. Com isso informamos limites assintóticos superiores, ou seja, que no pior cenário o tempo de execução cresce de uma maneira até atingir determinado limite, mas poderia crescer mais devagar. Não podemos desconsiderar que o input tem que ser suficientemente grande (repare na linha pontilhada). Não é incomum vermos algoritmos que performam em O(n log n) tendo um desempenho ruim com um conjunto de dados pequeno.
Agora sim! Vamos contar
Complexidade constante: O(1)
Queremos calcular qual é a complexidade de um algoritmo de troca de valores:
swap(num1, num2):
temp_num = num1
num1 = num2
num2 = temp_num
Podemos, em teoria, contar cada atribuição de valor executada pelo algoritmo como um “passo”. Teríamos complexidade = 3, e esse resultado nunca mudará, não importa qual valor que passe de entrada. Logo, é possível dizer que a complexidade desse algoritmo é constante, representada por O(1).
Pode parecer confuso não utilizar O(3), mas seguindo a definição matemática apresentada anteriormente, quando eu assumo que meu algoritmo tem complexidade O(1), estou dizendo que o seu limite assintótico superior é menor ou igual a k * f(n). Se considerarmos o k como constante representando a quantidade de atribuições do nosso algoritmo (3) e f(n) como o running time (1), temos como upper bound o valor 3.
Em outras palavras: Se o tempo de execução do seu algoritmo é constante, a maneira ideal de representá-lo é através de O(1).
Complexidade linear: O(n)
Quando a entrada do algoritmo é variável em tamanho, temos um comportamento diferente:
soma(array):
total = 0
for num in array:
total = total + num
Geralmente quando temos algum loop, e ele está ligado ao input, dificilmente chegamos a um algoritmo de complexidade constante. No caso acima, podemos contar os passos da seguinte forma:
n = tamanho(array)total = 0: 1 operação- atribuição de valor a num:
noperações total = total + num:n * 2operações
Para cada elemento do array, executaremos uma soma (total + num) e uma atribuição (total = <resultado>). Chegamos à conclusão que complexidade = 1 + (n * 2). Mas como chegamos a O(n)?
Deixando a parte matemática de lado, quando trata-se de análise assintótica, estamos mais interessados no que realmente interfere na performance do algoritmo. Ou seja, os valores constantes (1 e 2) nessa análise são detalhes se comparados ao impacto que n causa ao tempo de execução. Portanto, uma das maneiras de encarar a mensuração do Big O é simplesmente ignorando as constantes e focando no que é dinâmico, nos levando a complexidade = n e em consequência ao O(n).
Considerações finais
E como num passe de mágica, depois de certa intimidade com o Big O Notation, você passa a assumir a complexidade de um algoritmo com uma breve “olhadela”. Ao ver um loop assume que é n, ao ver loop dentro de loop, que é n2, e assim por diante…
Nos próximos posts vamos explorar algoritmos de diferentes complexidades, entrando em detalhes para entender os seus tempos de execução e alternativas otimizadas.
Até a próxima!
