Ir para o conteúdo

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.