Estruturas de Dados

[RTF] [PostScript]

7. Análise de Algoritmos

Introdução

7.1. Idéias básicas

7.2. Problema básico na Análise de Algoritmos:

    1. O tempo de execução em um computador particular não é interessante.
    2. Muito mais interessante é uma comparação relativa entre algoritmos.

Modelo de computação: As operações são todas executadas seqüencialmente. A execução de toda e qualquer operação toma uma unidade de tempo. A memória do computador é infinita.

7.3. Complexidade de Tempo

7.3.1. Primeiro caso: Bubblesort

Bubblesort é o mais primitivo dos métodos de ordenação de um vetor. A idéia é percorrer um vetor de n posições n vezes, a cada vez comparando dois elementos e trocando-os caso o primeiro seja maior que o segundo: 

ordenaBolha                                     /* Bubblesort */
        inteiro i,j,x,a[n];
        início
                para i de 1 até n faça
                        para j de 2 até n faça
                                se (a[j-1]>a[j]) então
                                        x <- a[j-1]; 
                                        a[j-1] <- a[j]; 
                                        a[j] <- x;
                                fim se
                        fim para
                fim para
        fim

A comparação (a[j-1]>a[j]) vai ser executada n*(n-1) vezes. No caso de um vetor na ordem inversa, as operações da atribuição triangular poderão ser executadas até 3*n*(n-1) vezes, já uma troca de elementos não significa que um dos elementos trocados tenha encontrado o seu lugar definitivo.

7.3.2. Segundo caso: StraightSelection

O método da seleção direta é uma forma intuitiva de ordenarmos um vetor: escolhemos o menor elemento do vetor e o trocamos de posição com o primeiro elemento.

Depois começamos do segundo e escolhemos novamente o menor dentre os restantes e o trocamos de posição com o segundo e assim por diante. 

seleçãoDireta
        inteiro i,j,k,x,a[n];
        início
                para i de 1 até n-1 faça
                        k <- i;
                        x <- a[i];
                        para j de i +1 até n faça
                                se (a[j] < x) então
                                        k <- j;
                                        x <- a[k];
                                fim se
                        fim para
                        a[k] <- a[i];
                        a[i] <- x;
                fim para
        fim

Neste algoritmo o número de vezes que a comparação (a[j] < x) é executada é expresso por (n-1)+(n-2)+...+2+1 = (n/2)*(n-1).

O número de trocas a[k] <- a[i]; a[i] <- x é realizado no pior caso, onde o vetor está ordenado em ordem inversa, somente n-1 vezes, num total de 2*(n-1).

7.3.3. Interpretação

Como ja'foi dito, a única forma de se poder comparar dois algoritmos é descrevendo o seu comportamento temporal em função do tamanho do conjunto de dados de entrada, Talgoritmo = f(n), onde n é o tamanho dos dados.

Assim, se tomarmos as operações de troca de valores como critério-base, podemos dizer que:

Tbubblesort = 3*n*(n-1) sempre e
Tstraightselection = 2*(n-1) para o pior caso.

7.4. Interpretação da Complexidade de Tempo

O gráfico acima nos mostra qual é o aspecto essecial que deve ser expresso pelo cálculo de complexidade:


Qual é o comportamento assintótico predominante de um algoritmo
em função do tamanho do
conjunto de dados a ser processado.

7.4.1. Análise Assintótica

7.4.2. Diferentes Tempos de Execução

Problema da Subseqüência de Soma Máxima: Dada uma seqüência de números a1, a2, ... , an, positivos ou negativos, encontre uma subseqüência aj,...,ak dentro desta seqüência cuja soma seja máxima. A soma de uma seqüência contendo só números negativos é por definição 0.

Exemplo: Para a seqüência -2, 11, -4, 13, -5, -2, a resposta é 20 (a2,a3,a4).

Este problema oferece um bom exemplo para o estudo de como diferentes algoritmos que resolvem o mesmo problema possuem diferentes comportamentos, pois para ele existem muitas soluções diferentes.

Abaixo, um exemplo dos tempos de execução dos diferentes algoritmos da subseqüência de maior soma:

7.4.3. Alguns exemplos do comportamento de diferentes algoritmos para a solução do problema da subseqüência de soma máxima:

7.5. Cálculo da Complexidade de Tempo

Um exemplo intuitivo: Cálculo de 

        inteiro somaCubos (inteiro n)
                inteiro i, somaParcial;
                início
1                       somaParcial <- 0;
2                       para i de 1 até n faça
3                               somaParcial <- somaParcial + i * i * i;
4                       fim para
5                       retorne somaParcial;
                fim

Análise:

7.5.1. Regras para o cálculo

  1. Laços Para-Faça e outros:
    O tempo de execução de um laço é, no máximo, a soma dos tempos de execução de todas as instruções dentro do laço (incluindo todos os testes) multiplicado pelo número de iterações.
  1. Laços Aninhados:
    Analise-os de dentro para fora.
    O tempo total de execução de uma instrução dentro de um grupo de laços aninhados é o tempo de execução da instrução multiplicado pelo produto dos tamanhos de todos os laços.
    Exemplo O(n2):
                para i de 1 até n
                        para j de 1 até n
                                k <- k + 1;
                        fim para
                fim para
  1. Instruções Consecutivas:
    Estes simplesmente somam, sendo os termos de ordem menor da soma ignorados.
    Exemplo O(n)+O(n2) = O(n2):

    2. para i de 1 até n
      a[i] <- 0;
    fim para
    para i de 1 até n
      para j de 1 até n
        a[i] <- a[j] + k + 1;
      fim para
    fim para

  2. IF/THEN/ELSE:
    Considerando-se o fragmento de código abaixo:

    se cond então
      expresssão    1
    senão
      expressão    2
    fim se

    o tempo de execução de um comando IF/THEN/ELSE nunca é maior do que o tempo de execução do teste cond em si mais o tempo de execução da maior dentre as expressões expressão1 e expressão2.
    Ou seja: se expressão1 é O(n3) e expressão2 é O(n), então o teste é O(n3) + 1 = O(n3).

  3. Chamada a Funções:
    Segue obviamente a mesma regra dos laços aninhados: analise tudo de dentro para fora. Ou seja: para calcular a complexidade de um programa com várias funções, calcule-se primeiro a complexidade de cada uma das funções e depois considere-se cada uma das funções como uma instrução com a complexidade de função.

  4. Recursão:
    Recursão é a parte mais difícil da análise de complexidade.
    Na verdade existem dois casos: Muitos algoritmos recursivos mais simples podem ser "linearizados", substituindo-se a chamada recursiva por alguns laços aninhados ou por uma outra subrotina extra e eventualmente uma pilha para controlá-la. Neste caso, o cálculo é simples e pode ser feito depois da "linearização".
    Em muitos algoritmos recursivos isto não é possível, neste caso obtemos uma relação de recorrência que tem de ser resolvida e é uma tarefa matemática menos trivial.

Exemplo de cálculo de complexidade em recursão: Fatorial

inteiro Fatorial (inteiro n)
  início
    se n <= 1 então
      retorne 1;
    senão
      retorne ( n * Fatorial ( n - 1 ) );
    fim se
  fim

O exemplo acima é realmente um exemplo pobre de recursão e pode ser "iterativisado" de forma extremamente simples com apenas um laço para-faça:

inteiro FatorialIterativo (inteiro n)
  inteiro i, fatorial;
  início
    fatorial <- 1;
    para i de 2 até n faça
      fatorial <- fatorial * i;
    fim para
    retorne fatorial;
  fim

A complexidade de FatorialIterativo pode então ser facilmente calculada e é evidente que é O(n).

O caso dos números de Fibonacci abaixo não é tão simples e requer a resolução de uma relação de recorrência:

inteiro Fibonacci (inteiro n)
  início
    se n <= 1 então
      retorne 1;
    senão
      retorne ( Fibonacci(n-1) + Fibonacci(n-2) );
    fim se
  fim


Observando o algoritmo, vemos que para n>= 2 temos um tempo de execução T(n) = T(n-1)+T(n-2)+2.
A resolução desta relação nos mostra que Fibonacci é O(()n)

7.5.2. Logaritmos e Outros no Tempo de Execução

7.6. Checando a sua análise

Uma vez que a análise de complexidade tenha sido executada, é interessante verificar-se se a resposta está correta e é tão boa quanto possível.

Uma forma de se fazer isto é o procedimento pouco matemático de se codificar o trecho de algoritmo cuja complexidade se tentou descrever e verificar se o tempo de execução coincide com o tempo previsto pela análise.

Quando n dobra, o tempo de execução se eleva de um fator 2 para algoritmos lineares, fator 4 para quadráticos e 8 para cúbicos.

Programas logarítmicos só aumentam o seu tempo de execução de uma constante a cada vez que n dobra. Algoritmos de O(n log n) tomam um pouco mais do que o dobro do tempo sob as mesmas circunstâncias.

Estes aumentos podem ser difíceis de se detectar se os termos de ordem inferior têm coeficientes relativamente grandes e n não é grande o suficiente. Um exemplo é o pulo tempo de execução para n=10 do para n=100 em algumas implementações do problema da subseqüência de soma máxima.

Distinguir programas n log n de programas lineares só em evidência de tempo de execução pode também ser muito difícil.

Uma boa praxe é, caso o programa não seja exponencial (o que você vai descobrir muito rápido), fazer alguns experimentos com conjuntos maiores de dados de entrada

7.7. Exercício: Calcule a Complexidade

Algoritmo extraído de: Márcia de Aguiar Rabuske,; Introdução à Teoria de Grafos, Editora da UFSC, 1990.