Anlise de Algoritmos para Iniciantes

Analisar o tempo de execuo de um algoritmo outro fantasma que assombra programadores iniciantes. Pode me chamar de caa-fantasmas que hoje voc vai terminar de ler este artigo e vai sentir um alvio por finalmente entender o que anlise de algoritmos e como isso funciona. Quando conhecemos nossos fantasmas eles j no nos assustam mais.

Este tipo de analise prope prever recursos computacionais (o quanto de memria ou banda de internet) que o algoritmo precisa para ser executado. Computadores da vida real trabalham fundamentalmente (ou seja, na sua forma mais bsica) com equaes aritmticas (somar, subtrair, multiplicar, dividir, funo piso e funo teto), movimentao de dados (carregar, copiar e armazenar) e controle (condies if, chamadas de subrotina e retorna). No se preocupe se voc no entendeu algumas palavras, eventualmente elas faro sentido e voc no precisa necessariamente sab-las para realizar uma anlise dessas.

Em geral o tempo de execuo de um algoritmo cresce de acordo com o tamanho da sua entrada. Ento uma forma tradicional (ou que utilizada com frequncia) descrever o tempo de execuo de um algoritmo como uma funo do tamanho da sua entrada. Por exemplo.: f(x) = x ou at Bhaskara.

Voc achou que nunca ia usar as equaes que aprendeu na escola n? Pois ento. Para fazer isso precisamos definir os termos tempo de execuo e tamanho da entrada com mais cuidado.

Tamanho da entrada

A melhor noo do tamanho da entrada depende do problema que est sendo estudado. Um algoritmo pode levar tempos de execuo diferente dependendo de como os dados esto ordenados ou at de como so representados. Por exemplo, multiplicar dois nmeros inteiros utiliza o espao de dois nmeros para a representao na memria, logo necessrio o espao em memria para armazenar os nmeros binrios que descrevem estes dois nmeros.

J em outros casos, a entrada pode ser um grafo, que uma estrutura que possui ns e arestas. A melhor forma de representar o tamanho da entrada de um grafo justamente atravs da quantidade de ns e arestas que este grafo possui. Cada projeto possui uma indicao do tamanho da medida da entrada que est sendo usado.

Se voc no entendeu ainda o conceito de memria e varivel d uma olhada no artigo anterior aqui (LINK).

Tempode execuo

O tempo de execuo de um algoritmo a partir de um determinado nmero de entrada simplesmente o nmero de passos executados. Isso acontece porque importante definir bem o tempo de execuo para que seja representada o mais INDEPENDENTE DA MQUINA possvel. Ento a notao (o jeito que escrito) de uma constante que vamos chamar de C ser Ci. Cada linha de instruo do algoritmo representar o tempo de execuo.

Exerccio opcional

Para cada funo 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 funo e observe o que acontece.

Analisando o Algoritmo

Para praticar esta tarefa de analisar o tempo de execuo de um algoritmos, precisamos de um modelo de implementao. Tenha em mente que vamos identificar uma frmula simplificada que representa o tempo de execuo que mostra as caractersticas mais importantes de um algoritmo.

O algoritmo escolhido um algoritmo muito usado para iniciantes: o Insertion Sort. A notao do algoritmo ser representada em ingls e em pseudocdigo, que a lngua 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 pseudocdigo

Repare que a funo chamada insertion-sort(A). A letra A uma varivel que guarda o vetor que recebido como argumento da funo para ser ordenado.

Um loop for que percorre de uma varivel j que inicia com o valor 2 armazenado. Cada interao o valor de j alterado para o prximo nmero e isso ocorre at o tamanho do vetor A. Traduzindo em python:

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

O incio da funo "do" significa "faa" neste contexto e est dentro do for. Executa uma sequencia de comandos enquanto o for executar. O comando uma atribuio de um valor A[j] para a varivel key. Traduzindo em python:

2        key = A[j]

Esta funo define o valor de uma nova varivel i em uma posio menor que a posio atual. O objetivo dessa linha mover o valor chave em uma posio uma vez menor que a atual.

4        i = j - 1

O valor de uma nova varivel i em uma posio menor que a posio atual. O objetivo dessa linha mover o valor chave em uma posio uma vez menor que a atual.

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

O valor atual substituido no valor posterior. Imagine uma rgua que comea no 1, se voc adicionar +1, voc ir para a posio 2.

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

O comando 7 comum, que simplesmente subtrai 1 da varivel i.

7            i = i - 1

Uma outra atribuio (ou substituio) do valor que estava na varivel key para a varivel i+1.

8        A[i + 1] = key

Aqui a implementao completa em python traduzindo o pseudocdigo acima.

  def InsertionSort(A):1    for j in range(1, len(A)):2        key = A[j]3        # Insere o valor A[j] na sequncia A[1, j-1]4        i = j - 15        while i >= 0 and A[i] > key:6            A[i + 1] = A[i]7            i = i - 18        A[i + 1] = key9    return A

Para testar voc pode instalar o python, copiar o cdigo e executar!

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

Um exemplo desenhado do algoritmo funcionando. A varivel key a representada em preto. As em cinza a movimentao 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 execuo dele vamos montar uma tabela com o cdigo em python. Voc pode montar a tabela em seu caderno com qualquer algoritmo.

Clculo do Tempo de Execuo

Ateno que vamos entrar no campo da matemtica. So contas simples que s precisam de um pouco de ateno. Para cada comando se define um custo ci onde i se refere a uma linha especfica. 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 execuo definido pelo nmero de instrues n. Lembre-se que o custo no interfere no que est escrito no cdigo, e sim representa quantas vezes aquela linha executada.

Agora repare nesta tabela que criamos, onde na primeira coluna insere-se a linha de cdigo, na segunda o custo e na terceira o tempo de execuo.

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. Ento o custo dessa linha seria:

Voc deve estar se perguntando, por que nas linhas subsequentes comeando da linha 2, o tempo (n-1)? Repare que todos os prximos comandos esto dentro de um loop for. Isso significa que poder executar todas as vezes menos a ltima vez que no entrar no loop.

No segundo while na linha 5 vemos um somatrio. Isso acontece porque um loop dentro de um loop. Essa situao incomum precisa ser representada por algum clculo matemtico que condiza com a situao real. O somatrio a soluo mais prtica. A varivel t representa o mesmo tempo de execuo de n, mas repare a quantidade de vezes que ela somada, para perceber voc precisa conhecer somatrio ou pode testar expandir a equao do somatrio para n = 5 voc ir perceber. Faa isso no seu caderno, vai ser divertido.

Em resumo, para definir o tempo de execuo de cada linha, preciso imaginar quantas vezes ela ser executada e usar a equao necessria para representa-la. Dica: Normalmente nunca passa de um simples somatrio.

Aps definir qual o valor do tempo de execuo, multiplicamos cada constante pelo seu tempo de execuo, igual fizemos na primeira linha.

Note que esta uma equao simples. Caso voc no esteja entendendo, recomendo fortemente que voc pesquise como resolver equaes e somatrios. A anlise pode ser feita entre o melhor caso, pior caso e caso mdio.

Melhor caso

Imagine a situao onde o array j est ordenado. A = [1,2,3,4,5] Este o melhor caso. Ao invs de usarmos de fato o somatrio, caso voc realize as substituies realizando um teste de mesa e calcular o tempo de execuo vai ser possvel perceber a substituio realizada abaixo.

Esse tempo de execuo pode ser expresso como T(n) = an b (eu substitui todas as constantes por uma s, coisa da matemtica) para constantes a e b que dependem dos custos da declarao ci , portanto, uma funo linear de n.

Pior caso

Se o array estiver ordenado ao contrrio, ou seja, de forma decrescente, este o pior caso do tempo de execuo. Com isso podemos realizar a substituio dos somatrios por uma progresso aritmtica de soma finita. Quando um algoritmo contm uma construo de controle iterativa, como um loop while ou for, seu tempo de execuo pode ser expresso como a soma dos tempos gastos em cada execuo do corpo do loop. Avaliar essa soma produziu equaes no tempo de execuo do pior caso do algoritmo.

Substituindo os somatrios por essas progresses na nossa equao principal.

Resolvendo temos que o pior caso pode ser expresa em uma equao de crescimento quadrtico em funo de n.

T(n) = an+bn+c

Anlise do melhor e pior caso

O tempo de execuo do pior caso de um algoritmo um limite superior no tempo de execuo para qualquer entrada. Saber disso nos d uma garantia de que o algoritmo no demorar mais. No precisamos fazer suposies sobre o tempo de execuo e esperar que nunca fique muito pior.

Para alguns algoritmos, o pior caso ocorre com bastante frequncia. Por exemplo, ao pesquisar em um banco de dados uma determinada informao, o pior caso do algoritmo de pesquisa geralmente ocorrer quando a informao no estiver presente no banco de dados. Em alguns aplicativos de busca, as buscas por informaes ausentes podem ser frequentes.

O caso mdio quase to ruim quanto o pior caso. Se calcularmos o tempo de execuo do caso mdio resultante, ele ser uma funo quadrtica do tamanho da entrada, assim como o tempo de execuo do pior caso.

Concluso

Usamos algumas abstraes simplificadoras para facilitar nossa anlise do procedimento INSERTION-SORT. Primeiro, ignoramos o custo real de cada declarao, usando as constantes ci para representar esses custos e ainda simplificamos pelas variveis "a" e "b". Assim, ignoramos no apenas os custos reais da declarao, mas tambm os custos abstratos ci.

Faremos agora mais uma abstrao simplificadora. a taxa de crescimento, ou ordem de crescimento, do tempo de execuo que realmente nos interessa. Portanto, consideramos apenas o termo principal de uma frmula (por exemplo, an), uma vez que os termos de ordem inferior so relativamente insignificantes para n grande. Tambm ignoramos o coeficiente constante do termo principal, uma vez que os fatores constantes so menos significativos do que a taxa de crescimento na determinao da eficincia computacional para grandes entradas.

Assim, escrevemos que o algoritmo de insero tem como pior caso o tempo de execuo (n). Isso chamado de notao assinttica que veremos no prximo artigo.