Análise de Algoritmos

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 c_i passos para ser executada, e é executada n vezes, contribuirá com c_in para o tempo total da execução. Esse tempo total é a soma dos produtos das colunas custos e quantidade de vezes (c₁n + c₂n + c_nn).

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 c_i, 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 (an² + bn + c), onde a, b e c depende do dos custos de instrução c_i, 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: an²), 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(n²).

Exercícios (Livro Algoritmos Teoria e Prática – Thomas Cormen 2012):

1-     Expresse a função n³/1000 - 100n² - 100n + 3 em termos da notação q.

n³

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 = (a₁, a₂, ..., a_n) 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 qn².

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.