Segundo
Thomas Cormen, analisar um algoritmo significa prever os recursos de que ele
necessitará, como memória, largura de banda, hardware, e principalmente, tempo
de execução.
Alguns
algoritmos podem aumentar seu tempo de execução de acordo com o tamanho da sua
entrada. Por exemplo, no algoritmo de ordenação, quanto mais elementos tiver a
entrada, mais irá demorar.
O
tamanho da entrada é o número total de itens na entrada. Por exemplo, o tamanho
de um arranjo que será ordenado.
O
tempo de execução é o número de operações primitivas ou etapas executadas.
Para
calcular o tempo de execução de um algoritmo, existe uma fórmula complicada de
explicar, que ao final se torna uma fórmula simples. Primeiro apresenta-se o
custo de tempo de cada instrução (que, apesar de na prática não ser assim, fica
convencionado que esse custo é um valor constante), e em seguida o número de
vezes que cada instrução é executada. Assim, o tempo de execução é a soma dos
tempos de execução para cada instrução executada; uma instrução que demanda ci passos para ser executada,
e é executada n vezes, contribuirá
com cin para o tempo total
da execução. Esse tempo total é a soma dos produtos das colunas custos e
quantidade de vezes (c1n +
c2n + cnn).
Esse
cálculo poderá resultar em uma função linear de n (an + b), onde a e b depende do dos
custos de instrução ci, representando
o melhor caso de tempo de execução (exemplo: executar o algoritmo de ordenação
em um arranjo já ordenado). Esse mesmo cálculo também poderá resultar em uma
função quadrática de n (an2 + bn + c), onde a, b
e c depende do dos custos de
instrução ci, representando
o pior caso de tempo de execução (exemplo: executar o algoritmo de ordenação em
um arranjo ordenado em ordem decrescente).
Apesar
do cálculo complexo explicado anteriormente, existe uma forma mais simples de
medir a eficiência de um algoritmo, através do cálculo da taxa ou ordem de
crescimento do tempo de execução. Para fazer esse cálculo, basta selecionar o
termo inicial da fórmula de tempo de execução do pior caso do algoritmo (no
exemplo anterior: an2), e
desconsiderar deste apenas o coeficiente constante, tendo em vista que fatores
constantes são menos significativos que a taxa de crescimento na determinação
da eficiência computacional para grandes entradas. Portanto, o algoritmo possui
ordem de crescimento igual q(n2).
Exercícios (Livro
Algoritmos Teoria e Prática – Thomas Cormen 2012):
1-
Expresse
a função n3/1000 - 100n2
- 100n + 3 em termos da notação q.
n3
2-
Considere
a ordenação de n números armazenados
no arranjo A, localizando primeiro o
menor elemento de A e permutando esse
elemento com o elemento contido em A[1].
Em seguida, encontre o segundo menor elemento de A e o troque pelo elemento A[2].
Continue dessa maneira para os primeiros n
- 1 elementos de A. Escreva o
pseudocódigo para esse algoritmo, conhecido como ordenação por seleção. Que
loop invariante esse algoritmo mantém? Por que ele só precisa ser executado
para os primeiros n - 1 elementos, e
não para todos os n elementos?
OrdenacaoSelecao(A)
para j ¬ 1 até comprimento(A)
- 1 faça
i ¬ j + 1
menor ¬ A[j]
temp ¬ A[j]
posicao ¬ j
enquanto i <= comprimento(A)
faça
se A[i] < menor então
menor ¬ A[i]
posicao ¬ i
i ¬ i + 1
A[j] ¬ menor
A[posicao] ¬ temp
O algoritmo só precisa ser executado até n – 1 por causa da permuta de valores no arranjo; ao chegar ao
elemento n -1, o mesmo só poderá ser
permutado com o elemento n, o qual não
terá mais elementos com o que ser comparado.
3-
Considere
o problema de pesquisa: Entrada: Uma sequência de n números A = (a1, a2, ..., an)
e um valor v. Saída: Um índice i tal que v = A[i] ou o valor
especial NIL, se v não aparecer em A. Quantos
elementos da sequência de entrada precisam ser verificados em média, supondo-se
que o elemento que está sendo procurado tenha a mesma probabilidade de ser
qualquer elemento no arranjo? E no pior caso? Quais são os tempos de execução
do caso médio e do pior caso da pesquisa linear em notação q? Justifique suas respostas.
Todos os elementos precisam ser testados até o final do arranjo.
Dado que o algoritmo apresenta apenas um loop, teríamos no pior dos casos o
tempo de execução qn2.
4-
Como
podemos modificar praticamente qualquer algoritmo para ter um bom tempo de
execução no melhor caso?
Inserindo a melhor opção de entrada. No caso de um algoritmo de
ordenação a melhor entrada é a de um arranjo já ordenado.
