Esta página procura explicar o que é análise de algoritmos. A explicação usa o algoritmo de ordenação por inserção como exemplo. Esse algoritmo resolve o seguinte
Problema da ordenação: Rearranjar um vetor A[1..n] de modo que ele fique em ordem crescente.
A página é baseada na seção 2 do capítulo 2 do CLRS.
Eis um algoritmo que resolve o problema da ordenação:
| Ordenação-Por-Inserção (A, n) |
| 1 o para j crescendo de 2 até n faça |
| 2 oooo x ← A[j] |
| 3 oooo i ← j−1 |
| 4 oooo enquanto i > 0 e A[i] > x faça |
| 5 ooooooo A[i+1] ← A[i] |
| 6 ooooooo i ← i−1 |
| 7 oooo A[i+1] ← x |
A melhor maneira de mostrar que um algoritmo iterativo faz o que promete é exibir um bom invariante do processo iterativo. No presente caso, isso é fácil: no início de cada repetição do "para", imediatamente antes de verificar a condição "i > 0 e A[i] > x",
o vetor A[1..j−1] é crescente.
Esse invariante é trivialmente verdadeiro na primeira repetição do "para" (pois j = 2 nesse caso). Se o invariante for verdadeiro na última repetição do "para" (quando j = n+1) então nosso problema está resolvido.
| 1 | crescente | j−1 | j | n | ||||||
| 444 | 555 | 555 | 666 | 777 | 222 | 999 | 222 | 999 | 222 | 999 |
A pergunta fundamental da análise de algoritmos é Quanto tempo o algoritmo consome? À primeira vista, a pergunta não faz sentido porque o tempo depende
Para responder a primeira objeção, digo que estou interessado no pior caso: para cada valor de n, considero a instância A[1..n] para a qual o algoritmo consome mais tempo. Vamos denotar esse tempo por T(n).
Para responder a segunda objeção, observo que o tempo não depende tanto assim do computador. Ao mudar de um computador para outro, o consumo de tempo do algoritmo é apenas multiplicado por uma constante. Por exemplo, se T(n) = 250n2 em um computador, então T(n) = 500n2 em um computador duas vezes mais lento e T(n) = 25n2 em um computador dez vezes mais rápido.
Podemos tratar então da determinação de T(n) para o algoritmo de inserção. A coluna direita da figura abaixo registra o número de execuções de cada linha no pior caso.
| Ordenação-Por-Inserção (A, n) | ||
| 1 o para j crescendo de 2 até n faça | n | |
| 2 oooo x ← A[j] | n−1 | |
| 3 oooo i ← j−1 | n−1 | |
| 4 oooo enquanto i > 0 e A[i] > x faça | 2+3+...+n | |
| 5 ooooooo A[i+1] ← A[i] | 1+2+3+...+n−1 | |
| 6 ooooooo i ← i−1 | 1+2+3+...+n−1 | |
| 7 oooo A[i+1] ← x | n−1 |
Suponha agora que a execução de qualquer das linha do código consome 1 unidade de tempo. Então o tempo no pior caso será a soma da coluna direita da figura:
T(n) = (3/2)n2 + (7/2)n − 4.
Se tivéssemos levado em conta o tempo exato de execução de cada linha, obteríamos coeficientes diferentes de 3/2, 7/2 e −4, mas a expressão de T(n) ainda seria da forma an2 + bn + c.
O coeficiente 3/2 de n2 não é importante: ele não depende do algoritmo mas de nossa hipótese "1 unidade de tempo por linha". Já o "n2" é fundamental: ele é característico do algoritmo em si e não depende nem do computador nem dos detalhes da implementação do algoritmo. Em resumo, a única parte importante em T(n) é o "n2". Todo o resto depende da particular implementação do algoritmo e do particular computador que estivermos usando. Dizemos que a quantidade de tempo que o algoritmo Ordenação-Por-Inserção consome no pior caso é
Θ(n2) .
Dizemos que o algoritmo é quadrático.
Se você perguntar a um computólogo quanto tempo o algoritmo Ordenação-Por-Inserção consome (no pior caso) para processar um vetor com n elementos ele dirá "Θ(n²)". Você traduz isso mentalmente para
"existem números positivos c e d tais que o consumo de tempo do algoritmo fica entre cn² e dn² desde que n seja suficientemente grande".
À primeira vista a resposta parece muito vaga. Mas é impossível dar uma resposta mais precisa (a menos que se conheça muito bem o computador que será usado para executar o algoritmo).
A resposta é até bastante informativa num sentido relativo: ela garante que se o tamanho do vetor for multiplicado por 10, então o tempo de execução será multiplicado por 100 (desde que n seja suficientemente grande); isso não é tão agradável quanto multiplicar o tempo por 10, mas é menos desastroso que multiplicar o tempo por 1000.
Eis uma versão recursiva do algoritmo de ordenação por inserção:
| Inserção-Rec (A, n) |
| 1 o se n > 1 então |
| 2 oooo Inserção-Rec (A, n−1) |
| 3 oooo x ← A[n] |
| 4 oooo i ← n−1 |
| 5 oooo enquanto i > 0 e A[i] > x faça |
| 6 ooooooo A[i+1] ← A[i] |
| 7 ooooooo i ← i−1 |
| 8 oooo A[i+1] ← x |
Quanto tempo ele consome? Digamos que o consumo de tempo no pior caso é T(n). A figura abaixo dá o tempo de execução de cada linha do algoritmo, supondo que as linhas "simples" consomem 1 unidade de tempo.
| Inserção-Rec (A, n) | ||
| 1 o se n > 1 então | 1 | |
| 2 oooo Inserção-Rec (A, n−1) | T(n−1) | |
| 3 oooo x ← A[n] | 1 | |
| 4 oooo i ← n−1 | 1 | |
| 5 oooo enquanto i > 0 e A[i] > x faça | n | |
| 6 ooooooo A[i+1] ← A[i] | n−1 | |
| 7 ooooooo i ← i−1 | n−1 | |
| 8 oooo A[i+1] ← x | 1 |
É claro então que T satisfaz a recorrência
T(n) = T(n−1) + 3n + 2
para n = 2, 3, 4, etc., com valor inicial T(1) = 1. Já mostrei em outra página que uma "fórmula fechada" para T(n) é
T(n) = 3n2/2 + 7n/2 − 4.
Eu poderia ter simplificado as coisas. Se estou apenas interessado em saber que T(n) = Ο(n2), bastaria ter verificado, por indução a partir da recorrência, que
T(n) ≤ 2n2 ,
para n = 2, 3, 4, etc. E isso é fácil. (Foi necessário um pouco de experimentação para "casar" o coeficiente 2 na frente de n2 com o valor inicial 2 de n.)
N(n) = N(n−1) + n−1
para n = 2, 3, 4, 5, etc. com valor inicial N(0) = N(1) = 0. Deduza daí que N(n) = n²/2 − n/2 para todo n natural não nulo.