Análise de Algoritmos para Iniciantes

Analisar o tempo de execução de um algoritmo é outro fantasma que assombra programadores iniciantes. Pode me chamar de caça-fantasmas que hoje você vai terminar de ler este artigo e vai sentir um alívio por finalmente entender o que é análise de algoritmos e como isso funciona. Quando conhecemos nossos fantasmas eles já não nos assustam mais.

Este tipo de analise propõe prever recursos computacionais (o quanto de memória ou banda de internet) que o algoritmo precisa para ser executado. Computadores da vida real trabalham fundamentalmente (ou seja, na sua forma mais básica) com equações aritméticas (somar, subtrair, multiplicar, dividir, função piso e função teto), movimentação de dados (carregar, copiar e armazenar) e controle (condições if, chamadas de subrotina e retorna). Não se preocupe se você não entendeu algumas palavras, eventualmente elas farão sentido e você não precisa necessariamente sabê-las para realizar uma análise dessas.

Em geral o tempo de execução de um algoritmo cresce de acordo com o tamanho da sua entrada. Então uma forma tradicional (ou que é utilizada com frequência) é descrever o tempo de execução de um algoritmo como uma função do tamanho da sua entrada. Por exemplo.: f(x) = x² ou até Bhaskara.

Você achou que nunca ia usar as equações que aprendeu na escola né? Pois então. Para fazer isso precisamos definir os termos “tempo de execução” e “tamanho da entrada” com mais cuidado.

Tamanho da entrada

A melhor noção do tamanho da entrada depende do problema que está sendo estudado. Um algoritmo pode levar tempos de execução diferente dependendo de como os dados estão ordenados ou até de como são representados. Por exemplo, multiplicar dois números inteiros utiliza o espaço de dois números para a representação na memória, logo é necessário o espaço em memória para armazenar os números binários que descrevem estes dois números.

Já em outros casos, a entrada pode ser um grafo, que é uma estrutura que possui nós e arestas. A melhor forma de representar o tamanho da entrada de um grafo é justamente através da quantidade de nós e arestas que este grafo possui. Cada projeto possui uma indicação do tamanho da medida da entrada que está sendo usado.

Se você não entendeu ainda o conceito de memória e variável dê uma olhada no artigo anterior aqui (LINK).

Tempo de execução

O tempo de execução de um algoritmo a partir de um determinado número de entrada é simplesmente o número de passos executados. Isso acontece porque é importante definir bem o tempo de execução para que seja representada o mais INDEPENDENTE DA MÁQUINA possível. Então a notação (o jeito que é escrito) de uma constante que vamos chamar de C será Ci. Cada linha de instrução do algoritmo representará o tempo de execução.

Exercício opcional

Para cada função f(n) e tempo t na tabela a seguir, determine o maior tamanho n de um problema que pode ser resolvido no tempo t, supondo que o algoritmo para resolver o problema leve f(n) microssegundos.

Dica.: Substitua o valor de n equivalente em microsegundos dentro da função e observe o que acontece.

Analisando o Algoritmo

Para praticar esta tarefa de analisar o tempo de execução de um algoritmos, precisamos de um modelo de implementação. Tenha em mente que vamos identificar uma fórmula simplificada que representa o tempo de execução que mostra as características mais importantes de um algoritmo.

O algoritmo escolhido é um algoritmo muito usado para iniciantes: o Insertion Sort. A notação do algoritmo será representada em inglês e em pseudocódigo, que é a língua utilizada para representar algoritmos em todo o mundo. Na imagem 1 mostra o algoritmo, e eu vou explicar linha por linha.

Imagem 1: Algoritmo Insertion Sort escrito em pseudocódigo

Repare que a função é chamada insertion-sort(A). A letra A é uma variável que guarda o vetor que é recebido como argumento da função para ser ordenado.

Um loop for que percorre de uma variável j que inicia com o valor 2 armazenado. Cada interação o valor de j é alterado para o próximo número e isso ocorre até o tamanho do vetor A. Traduzindo em python:

1 for j in range(1, len(A)):

O início da função "do" significa "faça" neste contexto e está dentro do for. Executa uma sequencia de comandos enquanto o for executar. O comando é uma atribuição de um valor A[j] para a variável key. Traduzindo em python:

2        key = A[j]

Esta função define o valor de uma nova variável i em uma posição menor que a posição atual. O objetivo dessa linha é mover o valor chave em uma posição uma vez menor que a atual.

4        i = j - 1

O valor de uma nova variável i em uma posição menor que a posição atual. O objetivo dessa linha é mover o valor chave em uma posição uma vez menor que a atual.

5        while i >= 0 and A[i] > key:

O valor atual é substituido no valor posterior. Imagine uma régua que começa no 1, se você adicionar +1, você irá para a posição 2.

6            A[i + 1] = A[i]

O comando 7 é comum, que simplesmente subtrai 1 da variável i.

7            i = i - 1

Uma outra atribuição (ou substituição) do valor que estava na variável key para a variável i+1.

8        A[i + 1] = key

Aqui a implementação completa em python traduzindo o pseudocódigo acima.

  def InsertionSort(A):
1    for j in range(1, len(A)):
2        key = A[j]
3        # Insere o valor A[j] na sequência A[1, j-1]
4        i = j - 1
5        while i >= 0 and A[i] > key:
6            A[i + 1] = A[i]
7            i = i - 1
8        A[i + 1] = key
9    return A

Para testar você pode instalar o python, copiar o código e executar!

arr = [12, 11, 13, 5, 6]
InsertionSort(arr)

Um exemplo desenhado do algoritmo funcionando. A variável key é a representada em preto. As em cinza é a movimentação dentro do while.

É muito importante para entender o algoritmo que você observe o comportamento do algortimo em uma lista neste link. Para analisar o tempo de execução dele vamos montar uma tabela com o código em python. Você pode montar a tabela em seu caderno com qualquer algoritmo.

Cálculo do Tempo de Execução

Atenção que vamos entrar no campo da matemática. São contas simples que só precisam de um pouco de atenção. Para cada comando se define um custo ci onde i se refere a uma linha específica. A constante c serve para o custo computacional para executar aquela linha. Essa constante, mais tarde, pode ser substituida por um valor equivalente ao custo computacional. O tempo de execução é definido pelo número de instruções n. Lembre-se que o custo não interfere no que está escrito no código, e sim representa quantas vezes aquela linha é executada.

Agora repare nesta tabela que criamos, onde na primeira coluna insere-se a linha de código, na segunda o custo e na terceira o tempo de execução.

Como você deve ter percebido, a primeira linha executa n vezes com um custo c1. Lembra que n é o tamanho da entrada que vimos antes? Imagine o vetor A = [1,2,3,4,5], qual é o tamanho n desta entrada? Isso mesmo, 5 porque a quantidade de elementos do vetor é 5. Então o custo dessa linha seria:

Você deve estar se perguntando, por que nas linhas subsequentes começando da linha 2, o tempo é (n-1)? Repare que todos os próximos comandos estão dentro de um loop for. Isso significa que poderá executar todas as vezes menos a última vez que não entrar no loop.

No segundo while na linha 5 vemos um somatório. Isso acontece porque é um loop dentro de um loop. Essa situação incomum precisa ser representada por algum cálculo matemático que condiza com a situação real. O somatório é a solução mais prática. A variável t representa o mesmo tempo de execução de n, mas repare a quantidade de vezes que ela é somada, para perceber você precisa conhecer somatório ou pode testar expandir a equação do somatório para n = 5 você irá perceber. Faça isso no seu caderno, vai ser divertido.

Em resumo, para definir o tempo de execução de cada linha, é preciso imaginar quantas vezes ela será executada e usar a equação necessária para representa-la. Dica: Normalmente nunca passa de um simples somatório.

Após definir qual o valor do tempo de execução, multiplicamos cada constante pelo seu tempo de execução, igual fizemos na primeira linha.

Note que esta é uma equação simples. Caso você não esteja entendendo, recomendo fortemente que você pesquise como resolver equações e somatórios. A análise pode ser feita entre o melhor caso, pior caso e caso médio.

Melhor caso

Imagine a situação onde o array já está ordenado. A = [1,2,3,4,5] Este é o melhor caso. Ao invés de usarmos de fato o somatório, caso você realize as substituições realizando um teste de mesa e calcular o tempo de execução vai ser possível perceber a substituição realizada abaixo.

Esse tempo de execução pode ser expresso como T(n) = an − b (eu substitui todas as constantes por uma só, coisa da matemática) para constantes a e b que dependem dos custos da declaração ci é, portanto, uma função linear de n.

Pior caso

Se o array estiver ordenado ao contrário, ou seja, de forma decrescente, este é o pior caso do tempo de execução. Com isso podemos realizar a substituição dos somatórios por uma progressão aritmética de soma finita. Quando um algoritmo contém uma construção de controle iterativa, como um loop while ou for, seu tempo de execução pode ser expresso como a soma dos tempos gastos em cada execução do corpo do loop. Avaliar essa soma produziu equações no tempo de execução do pior caso do algoritmo.

Substituindo os somatórios por essas progressões na nossa equação principal.

Resolvendo temos que o pior caso pode ser expresa em uma equação de crescimento quadrático em função de n.

T(n) = an²+bn+c

Análise do melhor e pior caso

O tempo de execução do pior caso de um algoritmo é um limite superior no tempo de execução para qualquer entrada. Saber disso nos dá uma garantia de que o algoritmo não demorará mais. Não precisamos fazer suposições sobre o tempo de execução e esperar que nunca fique muito pior.

Para alguns algoritmos, o pior caso ocorre com bastante frequência. Por exemplo, ao pesquisar em um banco de dados uma determinada informação, o pior caso do algoritmo de pesquisa geralmente ocorrerá quando a informação não estiver presente no banco de dados. Em alguns aplicativos de busca, as buscas por informações ausentes podem ser frequentes.

O “caso médio” é quase tão ruim quanto o pior caso. Se calcularmos o tempo de execução do caso médio resultante, ele será uma função quadrática do tamanho da entrada, assim como o tempo de execução do pior caso.

Conclusão

Usamos algumas abstrações simplificadoras para facilitar nossa análise do procedimento INSERTION-SORT. Primeiro, ignoramos o custo real de cada declaração, usando as constantes ci para representar esses custos e ainda simplificamos pelas variáveis "a" e "b". Assim, ignoramos não apenas os custos reais da declaração, mas também os custos abstratos ci.

Faremos agora mais uma abstração simplificadora. É a taxa de crescimento, ou ordem de crescimento, do tempo de execução que realmente nos interessa. Portanto, consideramos apenas o termo principal de uma fórmula (por exemplo, an²), uma vez que os termos de ordem inferior são relativamente insignificantes para n grande. Também ignoramos o coeficiente constante do termo principal, uma vez que os fatores constantes são menos significativos do que a taxa de crescimento na determinação da eficiência computacional para grandes entradas.

Assim, escrevemos que o algoritmo de inserção tem como pior caso o tempo de execução Θ(n²). Isso é chamado de notação assintótica que veremos no próximo artigo.