Estrutura de Dados – Básica
Professor: Osvaldo Kotaro Takai.
Aula 3: Análise e implementação de algoritmos em C/C++
Mostrar como medir o tempo de execução de um algoritmo através de ferramentas matemáticas que
são independentes da máquina e da implementação.
Antes de iniciar o desenvolvimento deste assunto, cabe aqui salientar que, embora um programa seja
a implementação de um algoritmo, sujeito, portanto, às limitações físicas da máquina onde ele será
executado (como capacidade de memória, velocidade do processador e dos periféricos), os
algoritmos desta aula serão apresentados em linguagem C. Esta decisão foi tomada para permitir que
o aluno possa, além de compreender em detalhes o algoritmo apresentado, verificar o resultado de
sua execução utilizando o IDE Dev-C++.
Critérios para o julgamento de um programa
1.
2.
3.
4.
5.
6.
7.
Ele faz exatamente o que queremos que faça?
Ele o faz corretamente, de acordo com as especificações originais da tarefa?
Há uma documentação que descreva como usá-lo e como ele trabalha?
As sub-rotinas são criadas de tal modo que realizem subfunções lógicas?
O código é legível?
Ele é executado em tempo ótimo de execução?
Ele usa espaço de memória mínimo necessário para sua execução?
Dentre as perguntas acima, as que são vitais quando se constrói um programa são as duas últimas (6
e 7), pois têm relação com o desempenho do programa.
A avaliação de desempenho pode ser dividida em dois tipos: (a) estimativas prévias e (b) testes
posteriores.
Para entender a avaliação por Estimativas Prévias, suponha a existência de um comando x = x + 1
em algum lugar do programa. Deseja-se estimar: (1) o tempo gasto para executar uma única vez
esse comando, e (2) o número de vezes que ele será executado. O produto desses valores dará o
tempo total gasto pelo comando.
A obtenção do número de vezes que o comando é executado (2) é chamada de Contagem de
Freqüência, e ela pode variar de um conjunto de dados para outro. Assim, é necessário escolher
amostras adequadas de dados para se estimar a freqüência.
Quanto a (1), é impossível determinar exatamente quanto tempo leva para executar qualquer
comando, desde que exista informações como:
• A máquina em que o programa está sendo executado;
• O conjunto de instruções da linguagem de máquina;
• O tempo gasto por cada instrução de máquina;
• A tradução que o compilador fará da linguagem fonte para a linguagem de máquina.
Mesmo assim, isso seria insuficiente, pois os compiladores podem variar em diferentes máquinas e
existam imprevisibilidades em ambientes de multiprogramação, multiprocessamento ou
processamento distribuído. Assim, a análise de algoritmos se limita contar apenas a freqüência de
todos os comandos de um programa considerando um tempo constante para todos os comandos.
1
Ordem de Magnitude
Exemplo: Quantas vezes o comando x = x + 1 será executado em cada uma das situações?
.
x = x + 1;
.
(a)
Resposta: Freq.(a) = 1
for ( i = 1; i <= n; i++ )
x = x + 1;
.
(b)
for ( i = 1; i <= n; i++ )
for ( j = 1; j <= n; j++ )
x <= x + 1;
(c)
Resposta: Freq.(b) = n
Resposta: Freq.(c) = n2
1, n e n2 são ordens de magnitude diferentes e crescentes, assim como 1, 10, 100 seriam, se fosse
considerado n=10.
O principal interesse é determinar a ordem de magnitude de um algoritmo, o que significa que a
preocupação recai sobre os comandos executados com maior freqüência.
Exemplo: n-ésimo número de Fibonacci:
Este procedimento executa apenas 7n + 5 operações para calcular fib(n). Esta freqüência é expressa
como O(n), ignorando as constantes 7 e 5, significando que a ordem de magnitude é proporcional a
n. Ou seja, conforme n cresce, o tempo gasto pelo algoritmo cresce linearmente em função de n.
Definição: f(n) = O(g(n)) se e só se existem duas constantes c e n0 tal que |f(n)| ≤ c |g(n)|, para todo
n ≥ n0. Isto é, a partir de certo n0, f(n) não cresce mais que c.g(n); ou f(n) tem o mesmo tipo de
crescimento que g(n). n é um parâmetro que caracteriza o tamanho da entrada e/ou a saída do
algoritmo.
2
Observações:
• O(1) - tempo constante
• O(log2n) - ordem logarítmica
• O(n) - ordem linear
• O(n2) - ordem quadrática
• O(n3) - ordem cúbica
• O(2n) - ordem exponencial
Relação entre as ordens
Método
Dado um algoritmo, calcula-se a freqüência de seus comandos e realiza-se a soma de todas elas. A
ordem de magnitude do algoritmo é dada pela ordem do(s) comando(s) mais freqüente(s). Assim, se
a soma é dada por um polinômio:
P(n) = ck.nk + ck-1.nk-1 +...+ c1.n + c0, onde ck ≠ 0,
então P(n) = O( nk ).
Mas, se algum passo for executado, por exemplo, 2n vezes, a expressão passa a ser P(n) = O(2n).
Outros exemplos:
(n+1) / 2
O(n)
2n3 + 4n2 +3
O(n3)
n2 + 1/n + 3
O(n2)
n log2n + n + 2
O(n log2n)
ln n
O(log2n)
{ logba = ln a / ln b }
3
Em cada um desses problemas, o parâmetro n provê uma medida do tamanho do problema no
sentido de que o tempo requerido para solucioná-lo, ou o espaço de armazenamento necessário, ou
ambos, serão incrementados conforme n aumenta.
A ordem de magnitude dará exatamente a proporção em que ocorre esse incremento. Na verdade,
O() dá o limite superior do recurso (tempo ou espaço) necessário para o algoritmo.
Exemplo
Considere o seguinte programa:
A função acima calcula o máximo divisor comum entre m e n. É natural, então, perguntar se este
algoritmo é melhor ou pior do que o Algoritmo de Euclides estudado na aula 1:
Certamente, o tempo gasto por cada um é diretamente proporcional ao número de operações
efetuadas.
Considere que cada operação elementar, tais como a soma, subtração, atribuição, entre outras, leve
uma unidade de tempo para executar.
Sejam, então, TA(m, n) e TE(m, n) os números de operações da função mdc e do mdcEuclides,
respectivamente.
Tem-se que: TA(m, n) = 7(min(m, n) - mdc(m, n)) + 8
Logo, para um n fixo, o número mínimo de operações, quando o comando while é executado uma
única vez, será 8 e o máximo (o pior caso) será 7n + 8.
O valor de TE(m, n) é um pouco mais difícil de ser formulado. Considere a seqüência de iterações
para m=34 e n=21:
4
Iterações (i)
0
1
2
3
4
5
6
m
34
21
13
8
5
3
2
ni
21
13
8
5
3
2
1
Para descobrir quantas iterações são necessárias para valores quaisquer de m e n para n<m, em
função de n, é necessário encontrar alguma relação entre as iterações i e n.
Essa relação pode ser encontrada verificando que a cada 2 iterações, o valor de n reduz para mais
da metade de seu valor:
Iterações (i)
0
2
4
6
ni
21
8
3
1
≤
≤
≤
≤
21
10,5
5,25
2,625
série
n/20
n/21
n/22
n/23
O t-ésima termo da série encontrada é n / 2 t.
Verifique que, pelo padrão da série encontrada ( n / 2 t ), n é dividido por 2 t e, portanto, não pode ser
superior a n. Ou seja:
(1)
2 t ≤ n Î log2 (2 t) ≤ log2 (n) Î t ≤ log2 (n)
Verifique também que existe uma relação entre i (iterações) e t de 2 t:
(2)
i=2*t
Substituindo (1) em (2) tem-se:
(3)
i ≤ 2 * log2 (n)
Como para cada iteração i é executado 5 comandos, a quantidade de operações executadas pela
função mdcEuclide será:
(4)
TE(m, n) = 5 * i + 1 ≤ 10 * log2 (n) + 1
5
Conclusão:
Verificou-se que:
•
TA(m, n) = 7(min(m, n) - mdc(m, n)) + 8
•
TE(m, n) = 5 * i + 1 ≤ 10 * log2 (n) + 1
Î O(n)
Î O(log2 (n))
Como assintoticamente O(log2 (n)) ≤ O(n) conclui-se que o Algoritmo de Euclides é no pior caso,
mais eficiente do que o algoritmo mdc. Verifique a grande discrepância para n muito grande:
n
log2(n)
4
5
6
10
64
100
128
1000
1024
1000000
1000000000
2
2
2
3
6
6
7
9
10
19
29
Limite superior (“upper bound”)
O algoritmo trivial para multiplicar matrizes quadradas de ordem n é bem conhecido e sua
complexidade é O(n3). Sabe-se assim que a complexidade deste problema não deve superar O(n3),
uma vez que existe um algoritmo desta complexidade que o resolve. O limite superior deste problema
é O(n3).
O limite superior de um problema pode mudar se alguém descobrir um outro algoritmo melhor. Isso
de fato aconteceu com o algoritmo de Strassen que é de O(n log2(7)). Assim o limite superior do
problema de multiplicação de matrizes passou a ser O(n log2 (7)). Outros pesquisadores melhoraram
ainda este resultado. Atualmente o melhor resultado é o de Coppersmith e Winograd - de O(n2.376).
Note que o limite superior de um problema depende do algoritmo.
O limite superior de um problema é parecido com o record mundial de uma modalidade de atletismo.
Ele é estabelecido pelo melhor atleta (algoritmo) do momento. Assim como o record mundial, o limite
superior pode ser melhorado por um algoritmo (atleta) mais veloz.
“Limite Superior” dos 100 metros rasos:
Ano Atleta (Algoritmo) Tempo
1988 Carl Lewis
9s92
1993 Linford Christie
9s87
1993 Carl Lewis
9s86
1994 Leroy Burrell
9s84
1996 Donovan Bailey
9s84
1999 Maurice Greene
9s79
2002 Tim Montgomery
9s78
Limite inferior (“lower bound”)
Às vezes é possível demonstrar que para um dado problema, qualquer que seja o algoritmo a ser
usado, o problema requer pelo menos certo número de operações. Essa complexidade é chamada
limite inferior do problema. Note que o limite inferior depende do problema, mas não de um particular
algoritmo. Utiliza-se a letra Ω em lugar de O para denotar um limite inferior.
6
Para o problema de multiplicação de matrizes de ordem n, apenas para ler os elementos das duas
matrizes de entrada leva tempo O(n2). Assim um limite inferior trivial é Ω(n2).
Na analogia anterior, um limite inferior de uma modalidade de atletismo não dependeria mais do
atleta. Seria algum tempo mínimo que a modalidade exigisse para qualquer atleta.
Se um algoritmo tem uma complexidade que é igual ao limite inferior do problema, então ele é ótimo.
O algoritmo de Coppersmith e Winograd é de O(n2.376) mas o limite inferior é de Ω(n2). Portanto não
se pode dizer que ele é ótimo. Pode ser que este limite superior possa ainda ser melhorado. Pode
também ser que o limite inferior de Ω(n2) possa ser melhorado (isto é “aumentado”). Muitos
pesquisadores desta área dedicam seu tempo tentando encurtar este intervalo (“gap”) tentando
encurtar esta distância.
Algoritmos Ótimos
O ideal seria que os dois limites, inferior e superior, fossem iguais, pois neste caso o algoritmo
utilizaria a quantidade exata de recursos que é tanto necessária quanto suficiente para resolver um
problema.
Se um algoritmo A utiliza exatamente a quantidade necessária de recursos (limite Inferior), então, A
será o ótimo para a tarefa, no sentido de que a quantidade de recursos utilizada por qualquer outro
algoritmo será maior, ou no melhor caso igual à A.
A diferença entre o limite inferior e o superior fornece uma medida de quanto um algoritmo pode ser
melhorado. Nem sempre, no entanto, é possível se construir algoritmos ótimos.
Análise de Algoritmos X Análise de Classes de Algoritmos
O objetivo da análise de algoritmos é Identificar o "melhor algoritmo possível" da família de algoritmos
que solucionam um determinado problema. Por exemplo, na classe de algoritmos de ordenação de n
elementos (memória interna), o critério de avaliação é o tempo de execução, medido pelo número C
de comparações entre chaves.
O limite superior dessa Classe de Algoritmos de Ordenação é C ≈ n log2 n
2
O limite inferior dessa Classe de Algoritmos de Ordenação é C ≈ n
Æ
O(n.log2n)
Æ
O(n2)
Os Métodos Diretos de Ordenação (inserção, seleção e troca) possuem O(n2) no pior caso e os
métodos avançados possuem:
•
•
•
Shellsort (inserção melhorada): O(n1.2) no pior caso.
Heapsort (seleção melhorada): O(n log2 n) no pior caso.
Quicksort (troca melhorada): O(n log2 n) no melhor caso e caso médio; O(n2) no pior caso.
É importante destacar que os algoritmos podem não alcançar o limite mínimo.
Exemplo: Multiplicação de Matrizes n x n
•
•
•
Limite inferior da classe: O(n2)
Algoritmo mais rápido: O(n2.376)
Algoritmo usual: O(n3)
7
Exercícios
1. Calcule a complexidade de tempo da função abaixo.
2. O algoritmo implementado pela função somaCubos pode ser melhorada. Assim, pesquise
uma solução alternativa para o problema de somar cubos e mostre que a sua solução é
melhor do que a solução apresentada acima.
3. Dados os algoritmos 1 e 2 para o cálculo do produto de dois números naturais m e n, calcule
a complexidade dos dois e indique qual é o melhor.
8