Noções elementares de complexidade computacional [Wiki Portugal-a-Programar]
Está aqui: Wiki P@P » Algoritmos » Noções elementares de complexidade computacional
algoritmo:complexo
Noções elementares de complexidade computacional
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) {
for ( ; novaPosMinimo < ultimoElemento; novaPosMinimo++) {
minimo=a[[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]];
//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.
Percorrer o //array// todo (excepto o primeiro valor) á procura do elemento mais pequeno de todos.
(estamos na realidade a procurar o 2º mais pequeno)
E assim sucessivamente até só termos de percorrer o último elemento do array.
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):
Se somarmos tudo temos que segundo uma fórmula dá , mas como estamos a fazer uma análise no limite, podemos esquecer o facto de estar multiplicado por , 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úmeros, isto significa que se o tempo de olhar para um número for um dado valor X, então para olhar para números eu preciso de . 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 algures, é esse valor que extraímos) e podemos dizer com toda a exactidão matemática que este algoritmo tem ordem (representa-se ). Isto significa que este algoritmo no limite precisa de um tempo inferior ou igual a .
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 , 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 .1)
Algoritmos de ordenamento amplamente estudados com esta ordem de crescimento são:
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.
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.
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.