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.
A página é baseada na seção 2 do capítulo 2 do CLRS.
Considere o seguinte problema:
Problema da ordenação: Rearranjar um vetor A[1 .. n] de modo que ele fique em ordem crescente.
Eis um algoritmo que resolve o problema da ordenação inserindo cada elemento do vetor na posição apropriada da parte do vetor que já está ordenada:
| Ordenação-por-Inserção (A, n) |
| 1 . para j := 2 até n |
| 2 .ooo x := A[ j] |
| 3 .ooo i := j−1 |
| 4 .ooo enquanto i > 0 e A[i] > x |
| 5 .oooooo A[i+1] := A[i] |
| 6 .oooooo i := i−1 |
| 7 .ooo A[i+1] := x |
A melhor maneira de mostrar que um algoritmo iterativo
faz o que promete é exibir um
invariante
do processo iterativo.
No presente caso, isso é fácil:
no início de cada repetição do para
(linha 1),
imediatamente antes de verificar
se j ≤ n,
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),
nosso problema está resolvido.
| 1 | crescente | j−1 | j | n | |||||
| 333 | 555 | 555 | 666 | 888 | 444 | 999 | 222 | 999 | 222 |
O invariante de um algoritmo iterativo é análogo à hipótese de indução em uma prova por indução matemática.
para j de 2 a n, o algoritmo procura na parte inicial do vetor a posição correta para A[ j] …)
A pergunta fundamental da análise de algoritmos é Quanto tempo o algoritmo consome? É claro que a resposta vai depender
A contribuição da máquina é simples:
ela multiplica o consumo de tempo do algoritmo por um fator constante,
ou seja, por um número que não depende de n.
Por exemplo, se trocarmos nossa máquina por outra
duas vezes mais lenta,
o consumo de tempo será multiplicado por 2.
Por outro lado,
se usarmos uma máquina duas vezes mais rápida,
o consumo de tempo será multiplicado por ½ .
Portanto, podemos ignorar a contribuição da máquina e exprimir
o consumo em unidades de tempo
,
sem especificar o valor da unidade.
Podemos dizer então que o consumo de tempo do algoritmo é função apenas do vetor A[1 .. n]. Vamos imaginar, por enquanto, que o consumo depende tão somente do tamanho do vetor: para cada n, o algoritmo consome T(n) unidades de tempo. (As coisas não são tão simples, na realidade, pois nem todos os vetores de tamanho n consomem o mesmo tempo.)
Trataremos a seguir de calcular T(n)
para o algoritmo de inserção.
Vamos supor que cada execução de cada linha
do código consome 1 unidade de tempo e
calcular o número de execuções de cada linha.
Para alguma linhas, é possível determinar o número exato;
para outras, teremos o número de pior caso
:
| Ordenação-por-Inserção (A, n) | ||
| 1 . para j crescendo de 2 até n | = n | |
| 2 .ooo x := A[ j] | = n−1 | |
| 3 .ooo i := j−1 | = n−1 | |
| 4 .ooo enquanto i > 0 e A[i] > x | ≤ 2 + 3 + ... + n | |
| 5 .oooooo A[i+1] := A[i] | ≤ 1 + 2 + 3 + ... + n−1 | |
| 6 .oooooo i := i−1 | ≤ 1 + 2 + 3 + ... + n−1 | |
| 7 .ooo A[i+1] := x | = n−1 |
A soma dos números na coluna direita dá uma estimativa de T(n) no pior caso:
T(n) ≤ (3/2)n2 + (7/2)n − 4.
O coeficiente 3/2 de n² é artificial,
pois resultou da hipótese arbitrária de
1 unidade de tempo por linha
.
Mas o n²
é natural e característico do algoritmo em si.
Para valores grandes de n,
o termo n² é muito maior
que (7/2)n − 4.
Em resumo, n² é
a única parte sólida e significativa
de (3/2)n² + (7/2)n − 4.
Todo o resto depende da máquina
(e sistema operacional)
que estivermos usando
e de certos detalhes de implementação do algoritmo.
Basta dizer então que
o algoritmo Ordenação-por-Inserção consome
unidades de tempo. A seguinte tabela resume o cáculo do consumo de tempo do algoritmo usando notação assintótica:
| Ordenação-por-Inserção (A, n) | ||
| 1 . para j crescendo de 2 até n | Θ(n) | |
| 2 .ooo x := A[ j] | Θ(n) | |
| 3 .ooo i := j−1 | Θ(n) | |
| 4 .ooo enquanto i > 0 e A[i] > x | Ο(n²) | |
| 5 .oooooo A[i+1] := A[i] | Ο(n²) | |
| 6 .oooooo i := i−1 | Ο(n²) | |
| 7 .ooo A[i+1] := x | Θ(n) |
Os exercícios a seguir mostram que a cota superior Ο(n²) para o consumo de tempo de Ordenação-por-Inserção não é exagerada: para alguns vetores A[1 .. n], o algoritmo consome Ω(n²) unidades de tempo. Portanto, no pior caso, T(n) = Θ(n²).
O desempenho do algoritmo Ordenação-por-Inserção pode ser calculado de uma maneira indireta que é muito conveniente.
Considere o número de execuções da comparação A[i] > x na linha 4. O tempo que decorre entre duas comparações consecutivas não depende de n. Assim, o consumo de tempo do algoritmo é proporcional ao número de execuções da comparação.
É fácil constatar que o número de execuções da comparação A[i] > x não passa de (n² − n)/2. Portanto, o consumo de tempo do algoritmo é Ο(n²).
No pior caso, o número de comparações A[i] > x é pelo menos (n² − n)/2. Portanto, o consumo de tempo do algoritmo no pior caso é Ω(n²).
Se você perguntar a um computólogo quanto tempo o algoritmo
Ordenação-por-Inserção
consome para processar um vetor
com n elementos,
ele dirá Ο(n²)
.
Você traduz isso mentalmente para
existe um número positivo c tal que o consumo de tempo do algoritmo não passa de c n² para todo n 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 a máquina que será usada para executar o algoritmo).
A resposta é até bastante informativa num sentido relativo: ela garante que se o tamanho do vetor for multiplicado por 10, o tempo de execução será multiplicado no máximo por 100. Isso não é tão bom quanto multiplicar o tempo por 10, mas é menos desastroso que multiplicar o tempo por 1000.
Não há uma razão muito forte para reescrever o algoritmo de ordenação por inserção em estilo recursivo. Mas é um bom exercício fazer isso.
| Inserção-R (A, n) |
| 1 . se n > 1 |
| 2 .ooo Inserção-R (A, n−1) |
| 3 .ooo x := A[n] |
| 4 .ooo i := n−1 |
| 5 .ooo enquanto i > 0 e A[i] > x |
| 6 .oooooo A[i+1] := A[i] |
| 7 .oooooo i := i−1 |
| 8 .ooo A[i+1] := x |
Quanto tempo esse algoritmo consome? Denote por T(n) o consumo de tempo no pior caso. Supondo que cada linha (exceto a linha 2) consome 1 unidade de tempo, a figura mostra o consumo de uma execução de cada linha do algoritmo,
| Inserção-R (A, n) | ||
| 1 . se n > 1 | 1 | |
| 2 .ooo Inserção-R (A, n−1) | T(n−1) | |
| 3 .ooo x := A[n] | 1 | |
| 4 .ooo i := n−1 | 1 | |
| 5 .ooo enquanto i > 0 e A[i] > x | n | |
| 6 .oooooo A[i+1] := A[i] | n−1 | |
| 7 .oooooo i := i−1 | n−1 | |
| 8 .ooo A[i+1] := x | 1 |
Fica 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 mostrar que T(n) = Ο(n²), 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 n²
com o valor inicial 2 de n.)
N(n) = N(n−1) + n
para n = 2, 3, 4, 5, etc. com valor inicial N(0) = N(1) = 0. Deduza daí que N(n) = ½ (n² + n − 2) para todo n natural não-nulo.