• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

theproject

[Algoritmia] Noções elementares de complexidade computacional.

5 mensagens neste tópico

Este artigo destina-se aos principiantes na ciência computacional mas mais concretamente a quem já sabe programar um pouco mas tem poucos conhecimentos teóricos. Alguém que aprendeu a programar sozinho numa dada linguagem encaixa-se perfeitamente nesta categoria.

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.

Não vou entrar em grande detalhe nesta explicação pois este tema sozinho serve para uma ou 2 cadeiras de faculdade mas no fim deste artigo devem saber como comparar dois algoritmos.

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 alg. 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 miudos 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 ord. 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).

Termino este artigo dizendo que 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.

Agora já sábem o que querem dizer os O's no wikipedia e livros técnicos de algoritmia.

Cumprimentos

Tiago Almeida

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Grande artigo. É muito básico, aconselho a leitura a todos os programadores. Já conhecia o algoritmo do Selection Sort, mas não compreendia exactamente para o que servia. Agora que programo em PHP, consegui finalmente compreender a utilização do Selection Sort e chego á conclusão que é utilizado pelas bases de dados quando queremos ordenar os elementos segundo uma ordem ascendente.

Mais uma vez, parabéns pelo artigo. :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Os meus parabéns, o artigo está simples e conciso, em suma bem feito.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Por acaso nunca me passou muito pela cabeça medir a velocidade de dois algoritmos... este tut está excelente mesmo... mas penso que é díficil por vezes saber quantos elementos são analizados por determinado algoritmo. Quero dizer, isot não funciona só para algortimos de ordenação pois não? Nesse caso nem sempre temos arrays como objecto a analisar, e penso que pode ser um pouco díficil de determinar o tal número de elementos.

Gostava que posteriormente, quem sabe se para uma futura publicação na revista, pudesses aprofundar mais os casos que dizes que não vais aprofundar... :P

Excelente tut :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas, obrigado pelas boas críticas.

DeathSeeker: De facto os motores de bases de dados tem algoritmos de ordenação de objectos (não tem  necessariamente de ser números) mas se de facto queres ordenar rapidamente muitos objectos, como o meu tur explica talvez o selection sort não seja a melhor forma de o fazer, consegues fazer o mesmo trabalho mais rapidamente se usares outros algoritmos de ordenação mais rápidos, ie, com uma complexidade computacional mais baixa.

vbmaster: De facto esta análise não se aplica só a algoritmos de ordenação e como disseste e bem, por vezes é difícil contar o numero de objectos a serem processados. Daqui a uns tempos aprofundarei o assunto e usarei talvez exemplos reais de projectos k já tive de fazer e em que fui obrigado a fazer uma análise deste tipo para determinar a melhor solução a aplicar. Nada muito matemático como programadores estamos sempre mais interessados no fim e não no meio. Aliás até sou capaz de escrever um artigo onde explico o algoritmo que resolve o enigma das torres de Hanoi e aproveito o tema para fazer a mesma análise desse algoritmo.

Cumprimentos

Tiago Almeida

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites