Noções elementares de complexidade computacional
A complexidade computacional é uma ferramenta teórica para medir a velocidade de um algoritmo.
Muitas vezes como programadores costumamos dizer que um dado algoritmo é "pesado", ou lento. O que vou explicar aqui pretende dar uma ideia de como se pode matematicamente classificar a velocidade de um algoritmo, isto pode parecer inútil, mas é na verdade extremamente importante quando quisermos fazer qualquer aplicação onde a eficiência e a rapidez sejam importantes, visto que nesta situação temos de saber escolher o algoritmo correcto de entre as várias opções.
Consideremos, por exemplo, um algoritmo de ordenação simples como o Selectionsort. Quão rápido é este algoritmo? É mais rápido ou mais lento que o Heapsort (por exemplo)?
Certamente alguns dirão que isso depende da velocidade dos computadores se os algoritmos forem testados em máquinas diferentes, outros dirão que depende de quantos programas estavam a correr concorrentemente. Tudo isso é verdade, porém a complexidade computacional permite classificar um algoritmo independentemente destes factores. Como?
Olhemos para o código do simplista Selectionsort (aqui apresentado em pseudo-código estilo C):
funcao seleciontSort(int[[]] a, int ultimoElemento) {
int posicaoMinimo;
int minimo;
int iterador;
int novaPosMinimo=0;
for ( ; novaPosMinimo < ultimoElemento; novaPosMinimo++) {
minimo=a[[novaPosMinimo]];
posicaoMinimo=novaPosMinimo;
for ( iterador = novaPosMinimo + 1; iterador < ultimoElemento; iterador++) { //Percorrer o array todo à procura do mínimo
if( a[[iterador]] < minimo) { //Se este elemento for mais pequeno que o mínimo
posicaoMinimo = iterador; //já encontrado, entao este passa a ser o mínimo.
minimo=a[[iterador]];
}
}
//já percorremos o array todo e já sabemos qual é o mínimo
//logo, metemo-lo na posição 0 do array, ie, a primeira posição do array
//e metemos o que estava na posição 0 na antiga posição do mínimo.
temp = a[[posicaoMinimo]];
a[[novaPosMinimo]] = minimo;
a[[posicaoMinimo]]= temp;
}
}
Este algoritmo funciona da seguinte maneira:
Percorrer o //array// todo á procura do mais pequeno elemento de todos.
Trocar esse elemento com o que está na primeira posição do array.
Percorrer o //array// todo (excepto o primeiro valor) á procura do elemento mais pequeno de todos.
(estamos na realidade a procurar o 2º mais pequeno)
Trocar esse elemento com o que está na segunda posição do array.
E assim sucessivamente até só termos de percorrer o último elemento do array.
Como foi visto este algoritmo é trivialmente implementado usando um ciclo e umas variáveis de controlo.
Agora a grande questão: Como podemos medir a velocidade deste algoritmo?
A maneira mais simples de fazer tal cálculo é contar o número de elementos que o algoritmo compara. Vamos fazer isso (consideremos que o array tem N elementos):
- Na 1ª iteração comparamos N elementos.
- Na 2ª iteração comparamos (N-1) elementos
- Na 3ª iteração comparamos (N-2) elementos
- ...
- Na (N-1)ª iteração comparamos apenas 1 elemento.
Se somarmos tudo temos \(N + (N-1) + (N-2) + ... + 1\) que segundo uma fórmula dá \((N+1)*N/2 = (1/2)*N^2*N\), mas como estamos a fazer uma análise no limite, podemos esquecer o facto de \(N^2\) estar multiplicado por \((1/2)*N\), de facto, se o resultado desse uma expressão com várias parcelas em N, apenas interessaria a parcela mais "forte".
Ou seja, trocado por miúdos, temos que este algoritmo para ordenar um array com N números tem de "olhar" para \(N^2\) números, isto significa que se o tempo de olhar para um número for um dado valor X, então para olhar para \(N^2\) números eu preciso de \(X*N^2\). Este valor X de facto depende da velocidade da máquina em que o algoritmo está a correr e dos recursos disponíveis na altura, e ainda temos de considerar o tempo de "trocar" os números de sítio mais o tempo de executar o código auxiliar como actualizar as variáveis de controlo etc, no entanto, mesmo que fizessem as contas todas, iam chegar a uma expressão em que só aparecem constantes ou Ns elevados ao quadrado. Agora, sem entrar em grande detalhe matemático olham para a expressão e extraem o valor de N mais elevado (neste caso como aparece um \(N^2\) algures, é esse valor que extraímos) e podemos dizer com toda a exactidão matemática que este algoritmo tem ordem \(N^2\) (representa-se \(O(N^2)\)). Isto significa que este algoritmo no limite precisa de um tempo inferior ou igual a \(N^2\).
Agora para que é que toda esta parafernália matemática serve? Para comparar algoritmos! Não vou fazer a demonstração porque penso que é desnecessária, mas se vos disser que o heapsort tem uma ordem de crescimento (ou complexidade computacional) O(N*lg(N)) conseguem perceber porque é que o heapsort é quase sempre mais rápido que o selection sort. Eu disse quase sempre, ele só não é mais rápido quando os arrays a ordenar são muito pequenos, por exemplo, N é muito baixo, tipo 10 números.
Se mesmo assim não entenderam porque é que o heapsort é mais rápido comparem o selection sort com um magic sort (que não existe) que teria uma ordem N. Mesmo que não gostem de matemática penso que é conhecimento comum que N cresce mais lentamente para infinito do que \(N^2\), logo este magic sort seria mais rápido que o selection sort.
Para terminar com os algoritmos de ordenação, talvez seja importante saber que é impossível um algoritmo de ordenação baseado em comparações tenha uma ordem menor que \(N*lg(N)\).1
Algoritmos de ordenamento amplamente estudados com esta ordem de crescimento são:
- Quicksort
- Heapsort
- Mergesort
Outros mais lentos mas possivelmente mais fáceis de implementar são:
- Bubblesort
- Selectionsort
Para quem é preguiçoso e não quer aprender a fazer tais cálculos apresento de seguida algumas ordens que aparecem muitas vezes em algoritmos e a sua explicação (obviamente quanto mais baixa a ordem melhor):
- O(1) - O algoritmo demora sempre o mesmo tempo independentemente do número de objectos a processar.
- O(N) - O algoritmo demora um tempo proporcional ao número de elementos a processar.
- O(N2) - O algoritmo demora um tempo proporcional ao quadrado do número de elementos a processar.
- ...
- O(N!) - O tempo que o algoritmo demora é proporcional ao factorial do nº de elementos a processar.
- O(NN) - Um algoritmo deste tipo é diabolicamente lento, i.e., a não ser que o N seja muito pequeno um algoritmo com tal ordem vai demorar semanas, meses ou anos a terminar.
Esta análise da ordem de crescimento pode ser feita para os 3 casos possíveis:
- O melhor caso possível,
- O caso médio,
- O pior caso possível.
O melhor caso possível para um algoritmo de ordenação é quando a rotina já recebe um array ordenado. Pode parecer estúpido que um algoritmo faça qualquer coisa neste caso, mas por exemplo o Selectionsort leva o mesmo tempo se receber um array já ordenado ou não.
O pior caso possível depende muito do algoritmo, por exemplo, aquele caso específico em que o algoritmo faz muito mais cálculos.
O caso médio engloba todos os outros casos, por exemplo, no âmbito dos algoritmos de ordenação é o caso em que ele recebe um array com elementos aleatórios.
No entanto, excepto para situações muito específicas vocês querem comparar algoritmos no caso médio, pois é o caso que a vossa aplicação vai encontrar mais vezes (pelo menos teoricamente).
Esta teoria não serve apenas para comparar velocidades, mas também, por exemplo, a memória ocupada pelo algoritmo, e que não se aplica apenas a algoritmos de ordenação, de facto aplica-se a qualquer algoritmo seja ele iterativo ou recursivo.