Analise de Algoritmos

MAIKON FERNANDES DE SOUZA

ANÁLISE DE ALGORITMOS E NOTAÇÕES ASSINTÓTICAS

CURITIBA

2015

MAIKON FERNANDES DE SOUZA

ANÁLISE DE ALGORITMOS E NOTAÇÕES ASSINTÓTICAS

Trabalho apresentada como requisito parcial para à obtenção do grau de Bacharel em Sistema de Informação, Tópicos Avançados de Estrutura de Dados, Centro  Universitário - UniBrasil.

Orientador: Prof.(a).  Fabio Roberto Bonilha Sylvio

CURITIBA

2015

Análise de Algoritmos

Analisar um algoritmo é prever o que o algoritmo irá precisar. Às vezes o hardware é importante, mas acho que o que acontece com mais frequência, ao menos em olimpíadas, maratonas e problemas em casa, é precisarmos medir o tempo que ele irá demorar.

Eu expliquei em algum dos artigos anteriores que o tempo de um algoritmo depende geralmente do tamanho de sua entrada. Um algoritmo baseado nesse tamanho de sua entrada para compará-lo com outros algoritmos e ter uma noção de quanto tempo ele vai demorar.

Para o entendimento ficar mais fácil, vamos partir do seguinte algoritmo (que vamos chamar de Algoritmo 1):

1. para i [pic 1] 1 até n, faça

2.  para j [pic 2] 1 até i, faça

3.      imprima i [pic 3] j [pic 4] n

4.  fim-para

5. fim-para

O que este algoritmo faz é, depois de receber a entrada [pic 5] do usuário, imprimir o produto de [pic 6] com todos dois números [pic 7] e [pic 8], tal que [pic 9].

Para medir o custo do algoritmo, nossa análise consistirá em ver quantas vezes cada passo é executado. Mediremos o custo de cada linha (cada passo a ser executado), sempre em função de n, que para este algoritmo é a variável mais importante (aliás, a única variável). Por isso o pseudocódigo do Algoritmo 1 está com suas linhas numeradas. Vamos analisar…

• Linha 1: Será executada [pic 10] vezes.
• Linha 2: Será executada [pic 11] vezes.
• Linha 3: Será executada [pic 12] vezes.
• Linhas 4 e 5: Não tem custo. :)

Linha 1

O loop para voltará para si mesmo [pic 13] vezes, isso é, testará novamente sua condicional e incrementará um. Por sempre testar um condicional, no final ele terá que testar novamente para dizer que já passou de [pic 14]. Por isso, ele será executado [pic 15] vezes, ao invés de simplesmente [pic 16].

Linha 2

Este loop para será executado um número de vezes variável ([pic 17]), que irá de [pic 18] a [pic 19]. Portanto, ele será executado duas vezes (1 mais “o último condicional”) no primeiro loop de [pic 20], três (2 mais “o último condicional”) no segundo, e por aí vai. Com isso, ele será executado o número de vezes que equivale a soma de [pic 21] a [pic 22], mais [pic 23] que são “os últimos condicionais”.

Linha 3

Exatamente o mesmo número que a Linha 2, mas sem “os últimos condicionais” ([pic 24]).

Imprimir algo na tela pode demorar mais do que fazer uma operação, mas a análise de algoritmos é uma coisa bem rústica. Desprezamos todas as constantes, com isso só levando a sério a informação importante: neste caso, apenas [pic 25]. Então agora, vamos escrever o tempo de execução do algoritmo, que é a soma dos tempos de execução para cada instrução executada.

[pic 26]

Os parênteses não são necessários, mas foi colocado para ajudar na visualização separando o custo de cada instrução.

Simplificando esta operação, teremos:

[pic 27], uma função quadrática.

Ordem de Crescimento

Um algoritmo é uma coisa feita sem precisão, porque para entradas realmente grandes (que são casos onde precisamos do computador!). As constantes não importam. Agora vamos determinar a ordem de crescimento de um algoritmo resgatando do nosso algoritmo apenas o valor mais importante, o maior expoente de [pic 28] nele, neste caso, [pic 29]. Se tivéssemos [pic 30], por exemplo, também usaríamos apenas [pic 31] porque o [pic 32] que multiplica também é desprezível!

Como representar o custo desse algoritmo usando notações assintóticas com a ordem de crescimento do algoritmo.

Notações Assintóticas

As notações que usamos para descrever o tempo de execução de um algoritmo são cinco:

• [pic 33]
• [pic 34]
• [pic 35]
• [pic 36]
• [pic 37]

Embora essas notações sejam conjuntos, usamos o sinal de igualdade ([pic 38]) para expressar que [pic 39] pertence a algum deles, ao invés de usar o sinal de pertinência ([pic 40]).

A notação [pic 41]

Lê-se “theta de gê de ene”.

[pic 42], se existem constantes positivas [pic 43], [pic 44] e [pic 45] tais que [pic 46] para todo [pic 47].

...