IntroduçãoAnalisar um algoritmo significa prever os

recursos que o algoritmo necessitará. Podem ser recursos de memória, largura de banda, hardware ou tempo.

Podemos analisar • O tempo de processamento em função de seus dados de

entrada;• A memória total utilizada pelo programa;• O número de linhas do código do programa;• Se o programa chega corretamente ao resultado;• Se o programa é fácil de entender e de ser alterado;• Se os erros causados por dados incorretos ou

inesperados são tratados corretamente.

Entretanto uma análise detalhada da performance de um algoritmo, que leve em consideração todos esses fatores, é muito complicada e não muito significativa. De todos estes fatores tempo é o recurso mais freqüentemente medido.

Em geral pela análise podemos indicar se um algoritmo é mais eficiente que o outro.

Esta análise pode ser feita a partir de dois processos: pelo método empírico e pelo método analítico.

Usar o método empírico possui os seguintes problemas:Os resultados são dependentes do compiladorOs resultados são dependentes do hardwareQuando grandes quantidades de memória são usadas os

resultados podem depender deste aspectoApesar dos problemas acima o método empírico é

útil quando temos vários algoritmos distintos, que resolvem o mesmo problema, de mesma ordem de grandeza.

No método analítico procura-se determinar uma expressão que nos forneça o tempo de execução em função da quantidade de dados processados, isto é:

Tempo = f(N)A complexidade de um algoritmo é o termo

normalmente utilizado para se fazer referência à sua eficiência

Para se encontrar a expressão que nos dá o tempo de execução de um algoritmo teremos que determinar a quantidade de operações que serão executadas para um conjunto de dados de tamanho N.

Como exemplo, vamos determinar o tempo de execução para o cálculo do somatório de uma série aritmética simples:

1 I    := 1; 2 Soma := 0; 3 while I <= N do begin 4    Soma := Soma + I; 5    I    := I + 1; 6 end;

Na análise do programa acima vamos considerar que os tempos necessários para realizar as operações de atribuição, comparação e adição são dados por T:=, T<= e T+, respectivamente.

Na análise anterior os tempos das operações depende dos fatores listados anteriormente. Dessa forma, fica bastante difícil comparar a eficiência de dois algoritmos usando esse mecanismo uma vez que teremos que especificar também o ambiente em que a medição foi feita.

Para simplificar iremos usar um computador idealizado que executaria qualquer instrução em um mesmo tempo T.

Em nosso modelo também não tentaremos modelar a hierarquia de memória.

Esta análise convencional permite previsões excelentes do desempenho em máquinas reais.

O efeito de tal simplificação resulta em que não precisamos mais considerar as operações separadamente. Dessa forma, para determinar o tempo de processamento de um programa basta simplesmente contar o número total de operações

Análise dos Tempos de ProcessamentoConsideremos o problema de se determinar

o maior valor de um vetor fazendo uma busca seqüencial no vetor:

public class Max{ public static int max(int v[ ], int n){ int max = v[0]; for (int i = 1; i<n; i++) if (max < v[i]) max = v[i]; return max; }}

Tempos de processamento do melhor caso, do pior caso e do caso médio

Consideremos o problema de se determinar o maior valor de um vetor fazendo uma busca seqüencial no vetor:

1 max = A[0]; 2 i = 0; 3 while (i < N) { 4    if (A[i] > max) 5     max = A[i]; 6 i = i + 1;    }  

Agora surge um problema: quantas vezes a linha 5 será executada? Neste caso não sabemos pois depende dos valores existentes no vetor. O que fazer então? Três estratégias são adotadas:

• Determinar o tempo do pior caso• Determinar o tempo do melhor caso• Determinar o tempo do caso médio

O pior caso: Ordem crescente. Linha 5 é executada em todas as iterações do laço. Dessa forma, o tempo de processamento para o pior caso é dado por:

T(N) = 5N + 3  O melhor caso: Ordem decrescente. Linha 5 nunca é

executada. O tempo de processamento será então:T(N) = 4N + 3

O cálculo do tempo médio de processamento exige o prévio conhecimento da distribuição de probabilidades das diferentes entradas. Na maioria dos casos essa distribuição é desconhecida e freqüentemente é de tratamento matemático complexo.

Como a análise do pior caso nos dá um limite superior do tempo de processamento, ela é a mais utilizada.

Exercício

Considere o seguinte algoritmo...1 - soma = 0;2 - for(x = 0; x < N; x++)3 - {4 - if (vetor[x] % 2 == 0)5 - soma = soma + vetor[x];6 - }7 - media = soma / N;

Exercício 2Calcule, usando a simplificação vista, a

complexidade do seguinte algoritmo 1 - for(x = 0; x < N-1; X++) 2 - for( y = 0; y < N; y++) 3 - if(vetor[x] > vetor[y]) 4 - { 5 - aux = vetor[x]; 6 - vetor[x] = vetor[y]; 7 - vetor[y] = aux; 8 - }

Notação OQuando estamos analisando a ordem de

crescimento de um algoritmo normalmente estamos interessados em se ter uma idéia de como o método se comporta quando alteramos o valor de N. Para isso precisamos apenas analisar o termo de maior valor da expressão, ou seja o termo que cresce mais rápido.

Exemplo: T(N) = N2+2NO termo representativo da expressão nos

dá a sua ordem, sendo representado pela notação O, a qual é escrita colocando-se a letra O e, entre parênteses, o termo representativo da expressão.

Assim, o algoritmo acima seria expresso na notação O como sendo O(N2), que se lê da seguinte forma: o algoritmo tem complexidade O(N2) ou sua complexidade é de ordem N2.

A notação O pode ser derivada a partir de T(N) da seguinte maneira:

• Fazer o coeficiente de cada termo igual a um;

• Tomar o maior termo da função como sendo a ordem do algoritmo, descartando os termos restantes.

Normalmente dividem-se as complexidades dos algoritmos em sete categorias como mostradas na tabela abaixo:

Gráficos de cada complexidade em função de N

Exemplo:Exemplo:Obtenha a notação Obtenha a notação O O para: para:

Regras Para a Notação O

A seguir apresentamos algumas regras simples para a determinação da complexidade do tempo de processamento de algumas composições básicas de comandos em um programa.

Regra 1: Tempo constanteA ordem de um algoritmo cujo tempo independe de N é

constante e igual a O(1).

Regra 2: Composição seqüencialO tempo de processamento para o pior caso de uma

seqüência de comandos, tais como:S1;S2;...S3;é igual à ordem do maior tempo entre todos os comandos.

Regras Para a Notação O Regra 3: Iteração

O tempo de processamento para o pior caso de um laço do tipo:

for I := 1 to N   S;

é igual ao tempo de execução de S multiplicado pelo número de vezes que ele será executado no pior caso, isto é, a ordem é O(N x Ts(N)), onde Ts(N) é o tempo máximo de execução de S.

Regra 4: Execução condicionalO tempo de processamento para o pior caso de um comando if-then-else

if S1 then  S2else  S3;é igual ao maior tempo de execução entre os comandos S2 e S3.

ExemploSeja o problema para calcular a série de somas

S1, S2, ..., Sn, obtidas por:

cujo algoritmo é:1  J := 1;2  while J <= N do begin3     S[J] := 0;4     I    := 1;5     while I <= J do begin6        S[J] := S[J] + A[I];7        I := I + 1;8     end;9     J := J + 1;10 end;

Vejamos o cálculo da ordem do algoritmo:

Exercícios1) Cada uma das seguintes fórmulas

representa o número de operações de determinado algoritmo. Exprimir cada uma delas usando a notação O:a) n2 + 5n b) 3n2 + 5nc) (n + 7)(n – 2) d) 100n + 5e) 6Log2N + 9N

f) 3N4 + NLog2Ng) 5N2 + N3/2

2) Escrever um trecho de programa contendo um laço para calcular a soma de todos os números inteiros de 1 a n. Fazer uma análise do tempo requerido, contando o número de somas e atribuições efetuadas e a seguir concluir qual a ordem do algoritmo.

3) Calcular a complexidade do seguinte trecho de programa:

I := 1;while I <= N do begin   J := 1;   while J <= N do begin      K := 1;      while K <= N do begin         Writeln(I, J, K);         K := K + 1;      end;      J := J + 1;   end;   I := I + 1;end;