Algoritmos #08 - Introdução à análise de complexidade

Por Bruno Henrique - agosto 24, 2019

Dentro do universo da programação, é comum encontrar diversos algoritmos que realizam uma mesma função. Porém, apesar do objetivo final ser idêntico, eles são compostos por estruturas e comandos completamente diferentes entre si e, portanto, haverá uma certa discrepância no tempo gasto por cada um durante a execução. Como, na computação, o custo de um algoritmo é diretamente proporcional ao seu tempo de execução, é essencial buscar sempre a criação do código mais eficiente possível.

Entretanto, não é viável calcular o tempo exato gasto, pois, ele depende do hardware do computador em que o código será executado e da linguagem de programação utilizada e, portanto, é diferente para cada situação. Nesse contexto, surge a análise assintótica, caracterizada como uma forma de "medir" a eficiência de um algoritmo em um contexto ideal (independente de fatores externos), que será melhor explanada a seguir.

Análise assintótica

Para medir o custo de execução (ou complexidade) de um algoritmo, geralmente é definida uma função f : f(n) -> n, em que n é um número natural que representa a quantidade de execuções de um mesmo código, ou seja, quanto maior o valor de f(n), maior a complexidade do algoritmo, e vice-versa.

Tomemos os algoritmos de busca como exemplo:

Na busca sequencial:

O algoritmo de busca sequencial, que procura um determinado valor em um vetor, é um algoritmo iterativo. Portanto, durante sua execução, caso o valor desejado esteja na primeira posição do vetor, o algoritmo retornará o resultado na primeira execução. Caso ele esteja na última posição ou não esteja presente, todo o vetor deverá ser percorrido. Logo:

Melhor caso: f(n) = 1
Pior caso: f(n) = n

Na busca binária:

A ideia principal da busca binária é que, caso o valor não seja encontrado na execução atual, a próxima execução será realizada com metade do vetor. Portanto, em um vetor de 16 posições, se o valor não for encontrado na 1ª tentativa, será feita a busca utilizando-se 8 valores (ou menores ou maiores), se não, se o valor não for encontrado na 2ª tentativa (ou menores ou maiores), será feita a busca utilizando-se 4 valores, e assim consecutivamente. Na matemática, existe uma função que representa o mesmo que o número de vezes que dividimos pela metade, começando em n, até obtermos o valor 1: o logaritmo de base 2 de n. Logo:

Melhor caso: g(n) = 1
Pior caso: g(n) = log2n

Comparando o crescimento das funções f(n) e g(n), é visível que, quanto maior o vetor, maior a diferença de velocidade entre os algoritmos e, consequentemente, maior a diferença de custo entre eles. Vale ressaltar que a busca binária é indicada apenas para estruturas já ordenadas.