Ferramentas de Site


algoritmo:complexo

Esta é uma versão antiga do documento!


FIXME Passar as expressões matematicas para mathML e escapar alguns caracteres. O texto em si não precisa de ser revisto.

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 matemáticamente 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 selection sort. 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 Selection Sort (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 posicao 0 do array, ie, a primeira posicao do array
 		//e metemos o que estava na posicao 0 na antiga posicao do minimo.
 		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.

etc.. 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, mas como estamos a fazer uma análise no limite, podemos esquecer o facto de N^2 estar multiplicado por 1/2, 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, entao 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 N's 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 extraimos) 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 pekeninos, ie, N é muito baixo, tipo 10 números.

Se mesmo assim não entenderam porque o heapsort e mais rápido comparem o selection sort com um magic sort (que não existe) que teria uma ordem N. Mesmo que nao 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 até à data nunca foi inventado um algoritmo de ordenação baseado em comparações que tenha uma ordem menor que N*lgN , e acredita-se que tal algoritmo não exista. 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(N^2) O alg. 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 eleemntos a processar.
  • O(N^N) Um algoritmo deste tipo é diabólicamente lento,ie, 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 selection sort leva o mesmo tempo se receber um array já ordenado ou não.

O pior caso possível depende muito do algoritmo, ie, aquele caso específico em que o algoritmo faz muito mais cálculos.

O caso médio engloba todos os outros casos, ie, no âmbito dos algoritmos de ordenação é o caso em que ele recebe um array randomizado.

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 <u>qualquer</u> algoritmo seja ele iterativo ou recursivo.

algoritmo/complexo.1300093796.txt.gz · Última modificação em: 2018/05/14 21:37 (edição externa)