Entenda a complexidade de algoritmos com a notação Big-O.

Qual imagem vem à sua mente quando falamos da complexidade de um algoritmo? Imensas linhas de códigos? Ou talvez um código que demande várias leituras para entender seu funcionamento? Bom, para de fato entender a complexidade e eficiência de algoritmos, precisamos elucidar alguns conceitos:

A performance de um algoritmo depende do números de passos (ou etapas) que ele leva até cumprir sua tarefa. Estudiosos da área pegaram emprestado o termo Big O notation da matemática para descrever precisamente a eficiência de um algoritmo, possibilitando então analisar diferentes abordagens para um mesmo problema e enfim, decidir qual cumpre o seu papel de forma mais eficiente.

Introdução

Complexidade de tempo

Ao invés de focar em unidades de tempo, a notação Big-O coloca o número de passos em foco, logo, o fator do hardware que está rodando o código não entra em questão. Portanto, não estamos falando de tempo de execução e sim de sua complexidade ao longo do tempo.

A definição da notação Big-O

Pode-se determinar a notação Big-O como: a maneira que um algoritmo responde à diferentes tamanhos de um determinado tipo de dado. Por exemplo, como sua performance se difere quando passamos 10.000 elementos ao invés de apenas 1 elemento.

O grande O significa “Ordem de”, então ao se deparar com a notação O(N), podemos ler “De ordem N” — é uma aproximação da duração do algoritmo dado N elementos de entrada. Isso responde a seguinte questão: Como o número de etapas até completar sua tarefa muda, ao passo que os elementos de entrada crescem?

O(N) descreve quantas etapas um algoritmo necessita com base no número de elementos sobre o qual ele atua.

O melhor x pior cenário

Começando com um simples exemplo: Dado um vetor unidimensional de entrada array[N] , e um valor X , nosso algoritmo irá buscar o valor X percorrendo o vetor do início até o valor ser encontrado.

Dado que esse vetor possui 5 números: [3,1,6,2,7] se estivermos procurando por X=7 , o algoritmo necessitaria de 5 passos para achá-lo, mas se estivermos procurando por X=3 só necessitaria de 1 passo. Portanto o melhor cenário ocorre quando procuramos por um valor que está na primeira célula, e o pior cenário ocorre quando este valor está na última célula ou não existe no vetor.

A notação Big-O possui uma abordagem pessimista em relação à performance e sempre se refere ao pior cenário possível. Isso será de grande relevância quando descrevermos as complexidades abaixo e também quando você for computar a complexidade de seus próprios algoritmos. Sempre pense no pior cenário.

O(1) — Constante

O(1) significa que o algoritmo leva o mesmo número de etapas para ser executado independente da quantidade de dados passados.

Exemplo

📝 Determine se o n-ésimo termo de um vetor é um número ímpar

A resposta exibida no console será: True

Gráfico

Se formos representar o número de passos (eixo y) x o número de elementos de entrada (eixo x), O(1) é uma linha horizontal perfeita, uma vez que o número de etapas no algoritmo permanece o mesmo, independente de quantos dados existam no vetor. É denominado tempo constante.

O(N) — Linear

Um algoritmo que possui a notação O(N) levará tantas etapas quanto o número de elementos de dados sobre o qual ele atua. Então para cada 1 elemento adicionado ao vetor, o algoritmo levará uma etapa a mais para ser concluído.

Exemplo

📝 Percorrer um vetor e exibir cada um de seus elementos

Neste caso, acessamos todos os elementos do vetor um a um, logo o tempo calculado aumenta ao passo que o número de elementos no vetor aumenta.

A resposta exibida será: 0 2 3 4 5

Gráfico

O gráfico se comporta como uma linha diagonal, uma vez que para cada elemento de dado adicionado, o algoritmo realiza um passo a mais. É denominado tempo linear.

Vamos plotar os gráficos de O(1) e O(N) e assumir que o algoritmo O(1) realiza 50 passos:

Podemos observar algumas coisas interessantes;

• Quando a entrada possui uma quantidade de elementos menor do que 50, o O(N) é mais eficiente.
• Nos exatos 50 elementos, ambos algoritmos possuem o mesmo número de etapas para sua conclusão.
• Ao passo em que o número de elementos aumenta, O(N) realiza mais etapas até sua conclusão.

E como a notação Big-O é pessimista e analisa a performance do algoritmo ao passo em que os dados tendem ao infinito, O(N) é considerado menos eficiente do que O(1) .

O(N²)-Quadrático

Representa a complexidade de um algoritmo cuja performance é proporcional ao quadrado do tamanho dos dados na entrada. Se um vetor possui 1 elemento, ele fará 1 operação, se o mesmo possuir 10 elementos, ele fará 100 operações e assim por diante.

Exemplo

📝 Encontrar elementos duplicados em um vetor

A resposta exibida será: True.

Gráfico

O(logN) — Logarítmico

Descreve o comportamento de algoritmos que a cada vez que a entrada de dados dobra, o número de etapas é acrescido de 1.

Exemplo

📝 Algoritmo de busca binária

A resposta exibida será: True.

Nós testamos uma possibilidade por iteração, e nossa gama de possibilidades é dividida por 2 a cada iteração, logo, a complexidade de um algoritmo de busca binária é de O(logN) .

Até agora aprendemos as quatro mais importantes notações, existem algumas outras que cobriremos de forma mais breve:

O(N logN) — Log-Linear

Um algoritmo expresso por esta notação realiza um número de tarefas correspondente a N vezes o log(N)e apesar de sua performance ser ligeiramente pior do que O(N) , muitos algoritmos práticos pertencem a esta categoria, incluindo os de compactação, classificação e pathfinding. Podemos citar como exemplo o conhecido Merge Sort, um algoritmo de dividir para conquistar, ele atua dividindo a entrada em duas partes, chama a si mesma para cada uma e depois une as duas partes classificadas.

O(2ᴺ) — Exponencial

Os algoritmos assim classificados levam o dobro do tempo para rodar para cada elemento adicionado. Temos como exemplo o algoritmo de achar todas as subcategorias de um conjunto de dados devidamente classificado.

O(N!) — Fatorial

Estes algoritmos possuem sua complexidade de tempo pautada no fatorial do número de entradas: n! = n*(n-1)*(n-2)*(n-3)*...*1 . Podemos citar como exemplo o algoritmo que encontra todas as possíveis permutações em um conjunto de dados.

Hierarquia de crescimento

A notação Big-O nos oferece um mecanismo consistente para comparar quaisquer dois algoritmos que cumprem uma mesma tarefa, para enfim determinar qual fará nosso código mais rápido e eficiente. Colocando todos num mesmo gráficos, podemos observar de maneira visual como as diferentes notações se comportam em termos de performance.

Conclusão

Espero que tenham aproveitado a leitura e percebido que a notação Big-O é um conceito bem simples de ser compreendido e aplicado ao seu código para torná-lo cada vez mais eficaz e rápido!

Lembrem-se!

O(1) < O(logN) < O(N) < O(N logN) < O(N²) < O(2ᴺ) < O(N!)