Análise de algoritmos: como se faz?

Aprenda como se faz a análise de algoritmos. Veja exemplos e demonstrações passo a passo de análises realizadas em algoritmos reais.

Objetivo da análise de algoritmos

A análise de algoritmos é uma importante disciplina da Ciência da Computação. Ela tem o objetivo de fornecer métodos mais assertivos para medir o desempenho de algoritmos.

De maneira mais simples e direta possível, a análise de algoritmos pode ser realizada facilmente por métodos empíricos (baseados em experiências práticas), tal como o tempo em segundos que ele demora para processar uma entrada. Você poderia medir o tempo decorrido antes e depois da execução de um algoritmo e, com base nesse resultado, inferir sobre o seu desempenho.

O código abaixo ilustra um exemplo desse método de cálculo de tempo empírico usando a linguagem Java. Ele mede o tempo de execução do algoritmo que calcula o n-ésimo termo da sequência de Fibonacci (linhas 15-18).

1.public static void main(String[] args) {

2.     int n;

3.     long start, end;

4.     double cpu_time_used;

5.     Scanner sc = new Scanner(System.in);

6.     System.out.println("Digite o n-ésimo termo da sequência de Fibonacci");

7.     n = sc.nextInt();

8.     start = System.nanoTime();

9.     int result = fib(n);

10.     end = System.nanoTime();

11.     cpu_time_used = (double)(end-start) / 1_000_000_000.00;

12.     System.out.println("O "+n+"º termo de Fibonacci = "+result);

13.     System.out.println("O tempo de execução foi de "+cpu_time_used+" segundos.");

14.}

15.public static int fib(int n) {

16.     if(n==2 || n==1)

17.          return 1;

18.     return fib(n-1) + fib(n-2);

19.}

Na linha 8 é obtido o registro de tempo inicial em nano segundos. Na linha 9 é invocada a função fib(), que executa o algoritmo de Fibonacci. Na linha 10 é obtido o registro de tempo final, também em nano segundos. Na linha 11 é calculado o tempo de execução. Por fim, na linha 13, o tempo de execução é exibido.

Abaixo são apresentados os tempos de execução (em segundos) para algumas entradas desse algoritmo:

  • n=40: tempo de execução em torno de 0.4 segundos
  • n=41: tempo de execução em torno de 0.8 segundos
  • n=42: tempo de execução em torno de 1.2 segundos
  • n=43: tempo de execução em torno de 2 segundos
  • n=44: tempo de execução em torno de 3.1 segundos
  • n=45: tempo de execução em torno de 5 segundos

Entretanto, esta não é a melhor forma de realizar a análise de um algoritmo. Estes resultados foram gerados com o algoritmo escrito na linguagem Java, utilizando a IDE Eclipse, em um notebook Intel Core i7. Se estas especificações mudassem, com certeza os resultados seriam diferentes.

Desta forma, o tempo de execução de um algoritmo pode ser influenciado por diversos fatores, tais como: velocidade de processamento do computador, linguagens de programação utilizadas, compiladores, sistema operacional, para citar alguns.

Estes fatores invalidam a confiança dos resultados de desempenho, pois nunca se poderá saber ao certo o tempo de processamento do algoritmo de maneira precisa.

O método analítico para a análise de algoritmos

O método analítico é uma maneira mais assertiva de realizar a análise de algoritmos. Ele não tem o objetivo de calcular o tempo de execução em segundos, minutos ou alguma outra representação real de tempo. Ele visa encontrar uma expressão matemática para traduzir o desempenho em quantidade de etapas. Desta forma, consegue-se medir o desempenho do algoritmo de maneira totalmente independente de linguagens de programação, de compiladores, de ferramentas e de outros fatores físicos que possam invalidar a análise.

Para tanto, o modelo RAM (Random Access Machine) é a estratégia utilizada para medir desempenho de maneira analítica. Ele realiza a contagem das etapas que um algoritmo executa e ignora todos os aspectos de velocidade de processamento, linguagem de programação ou qualquer outro tipo de otimização de hardware. Neste modelo, cada operação (tais como, atribuições, comparações e inicializações) consome um custo computacional constante e único.

Veja abaixo diversos exemplos de operações computacionais comumente encontrada nos algoritmos, todas com o mesmo custo computacional:

Atribuição de valor

1.int valor = 0; // um único custo computacional

2.float sal = 2005.15; // um único custo computacional

Incremento ou decremento de valor

1.valor++; // um único custo computacional

2.valor--; // um único custo computacional

Operações matemáticas complexas

1.valor*(4/Math.sqrt(9)); // um único custo computacional

Acesso a elementos de arranjos

1.lista[i]; // um único custo computacional

Operações lógicas

1.if(valor > 10); // um único custo computacional

2.if(valor==3 || valor==2); // um único custo computacional

Operações de leitura e escrita

1.System.out.println("Ola mundo!"); // um único custo computacional

2.scanner.nextInt(); // um único custo computacional

É óbvio que, na realidade, estas instruções possuem diferenças significativas de desempenho. Umas são obviamente mais rápidas de serem executadas do que outras. Contudo, como estamos interessados em analisar o desempenho do algoritmo com base na quantidade de etapas, o modelo RAM ignora tais diferenças. Principalmente pelo fato de que elas têm mais a ver com os computadores do que com o algoritmo em si.

Análise de algoritmos por contagem de etapas

Com a quantificação das etapas geradas pelo modelo RAM podemos comparar vários algoritmos uns com os outros e afirmar de maneira mais precisa qual é o mais rápido, pois, independente da velocidade dos computadores nos quais são executados, um algoritmo que executa uma menor quantidade de etapas sempre apresentará melhor desempenho para grandes volumes de dados processados.

Abaixo segue um código de um programa simples que iremos utilizar como exemplo para começar a explicar a técnica analítica da contagem de etapas. Para realizar esse processo, basta contar, linha por linha, a quantidade de instruções realizadas por cada comando:

Algoritmo

1.Scanner sc = new Scanner(System.in); // criação de objeto = 1 instrução

2.int idade; // declaração de variável = 1 instrução

3.System.out.println("Digite a sua idade:"); // operação de escrita = 1 instrução

4.idade = sc.nextInt(); // operação de leitura e atribuição = 2 instruções

5.if (idade >= 18) // operação lógica = 1 instrução

6.     System.out.println("Maior de idade:"); // operação de escrita = 1 instrução

7.else

8.     System.out.println("Menor de idade:"); // operação de escrita = 1 instrução

Desta forma, temos que o algoritmo realiza um total de 7 instruções (o if-else são mutuamente exclusivos). Dizemos que T(n)=7 é a fórmula de complexidade de tempo desse algoritmo que, por ser uma função constante, possui complexidade constante.

Análise de algoritmos lineares

A análise realizada anteriormente foi bem fácil e serviu apenas para o aprendizado. Vamos ver um exemplo mais complicado. Um algoritmo que, dado um arranjo A[ ] de n valores, imprime todos os elementos desse arranjo.

Algoritmo

1.public static void printArray(int[] A){

2.     for(int i = 0; i < A.length; i++){

3.          System.out.println(A[i]+"\n");

4.     }

5.}

Vamos dissecar linha por linha a contagem desse algoritmo:

2.for(int i = 0; i < A.length; i++){ // 1 inicialização, n+1 comparações e n incrementos = 2n+2 instruções

3.System.out.println(A[i]+"\n"); // n operações de escrita = n instruções

Portanto, o algoritmo realiza um total de (2n+2)+n = 3n+2 instruções. Dizemos que T(n)=3n+2 é a fórmula de complexidade de tempo desse algoritmo que, por ser uma função do 1º grau, possui complexidade linear.

Vamos para a análise de um algoritmo um pouco mais complicado. Um algoritmo que, dado um arranjo A[ ] de n valores, calcula o maior valor desse arranjo. Perceba que o algoritmo possui uma estrutura de repetição “for” (linhas 3-7) que executa um condicional “if” (linha 4) n-1 vezes.

Algoritmo

1.public static int calculaMax(int[] A){

2.     int maior = A[0];

3.     for(int i =1; < A.length; i++){

4.          if(maior < A[i]){

5.               maior = A[i];

6.          }

7.     }

8.     return maior;

9.}

Vamos dissecar linha por linha a contagem desse algoritmo:

2.int maior = A[0]; // acesso a arranjo e atribuição = 2 instruções

3.for(int i = 1; i < A.length; i++){ // 1 inicialização, n comparações e n-1 incrementos = 2n instruções

4.if(maior < A[i]) // n-1 operações lógicas = n-1 instruções

8.return maior; // 1 retorno de valor = 1 instrução

Agora perceba que a quantidade de instruções de atribuição da linha 5 é muito difícil de ser premeditada. Não sabemos quando o condicional na linha 4 retornará verdadeiro, pois isso depende da estrutura das informações presentes no arranjo A[ ]. Depende da seguinte maneira:

  • Se o arranjo A[ ] estiver ordenado de maneira crescente, o maior elemento será o último e, portanto, a linha 5 será executada n-1 vezes (Pior caso).
  • Se o arranjo A[ ] estiver ordenado de maneira decrescente, o maior elemento será o primeiro e, portanto, a linha 5 nunca será executada (Melhor caso).

Dessa análise temos que o algoritmo irá possuir duas fórmulas de complexidade de tempo:

  • No pior caso a complexidade será: (2) + (2n) + (n-1) + (1) + (n-1) = T(n)=4n+1
  • No melhor caso a complexidade será: (2) + (2n) + (n-1) + (1) = T(n)=3n+2

Basicamente, o melhor caso é aquela situação em que o algoritmo recebe os dados da melhor forma possível para obter o máximo de desempenho. De maneira análoga, o pior caso é aquela situação em que o algoritmo recebe os dados da pior forma possível, e, por isso, tem o seu pior desempenho.

É de extrema importância descrever o conceito de melhor e pior caso no processo de análise de algoritmo pois nunca podemos prever o estado das entradas dos dados que irão ser processados pelo algoritmo.

Por esse motivo, iremos ignorar o conceito de melhor caso e nos concentraremos sempre em fazer a análise considerando sempre o pior caso, pois, dessa forma, podemos garantir que iremos calcular a fórmula de complexidade de tempo máxima do algoritmo. Ou seja, o seu tempo máximo de execução.

Análise de algoritmos quadráticos

Vamos agora partir para a análise de um algoritmo mais complexo. Um algoritmo de ordenação de informações que utiliza o famoso método bolha: o Bubble Sort.

Este algoritmo é bem mais complexo que o anterior pois é um algoritmo quadrático. O termo “quadrático” significa que a sua fórmula de complexidade é uma função do 2º grau, no pior caso.

Mas vamos realizar a análise para perceber como isso ocorre na prática.

Algoritmo

1.public static void bubbleSort(int[] A) {

2.     boolean trocou;

3.     do{

4.          trocou = false;

5.          for(int j = 0; j < A.length-1; j++) {

6.               if(A[j] > A[j+1]) {

7.                    troca(A, j, j+1);

8.                    trocou=true;

9.               }

10.          }

11.     } while(trocou==true);

12.}

Análise do algoritmo no pior caso

O algoritmo do Bubble Sort possui o pior caso quando o arranjo A[ ] se encontra totalmente desordenado (quando os elementos do arranjo estão em ordem decrescente).

2.boolean trocou; // declaração de variável = 1 instrução

4.trocou = false; // 1 atribuição (que ocorre n vezes, por estar dentro de um laço) = n instruções

5.for(int j=0; j < A.length-1; j++) { // 1 inicialização, n comparações e n-1 incrementos, n vezes = 2n2 instruções

6.if(A[j] > A[j+1]) { // n-1 operações lógicas, n vezes = n2-n instruções

7.troca(A, j, j+1); // n-1 trocas, n vezes = n2-n instruções

8.trocou=true; // n-1 atribuições, n vezes = n2-n instruções

11.while(trocou==true); // n operações lógicas = n instruções

Perceba que consideramos que as estruturas de repetição “do-while” (linhas 3-11) e “for” (linhas 5-10) sempre serão executadas. Ou seja, consideramos o pior caso da execução do algoritmo Bubble Sort.

Assim sendo, o somatório de suas instruções é igual a: 1 + n + 2n2 + 3(n2-n) + n. Ao reduzirmos essa expressão, temos que o algoritmo realiza um total de 5n2-n+1 instruções. Dizemos que T(n)=5n2-n+1 é a fórmula de complexidade de tempo desse algoritmo que, por ser uma função do 2º grau, possui complexidade quadrática no pior caso.

Mas acontece que o algoritmo do Bubble Sort possui uma particularidade com relação à estrutura de repetição “do-while” (linhas 3-11). Quando o arranjo A[ ] já se encontra ordenado (melhor caso), não ocorrem trocas e o laço “do-while” é executado apenas uma vez! Isso significa que temos para o melhor caso uma outra fórmula de complexidade de tempo. Vamos fazer essa análise.

Análise do algoritmo no melhor caso

2.boolean trocou; // declaração de variável = 1 instrução

4.trocou = false; 1 atribuição (que ocorre apenas 1 vez, por que o arranjo já está ordenado) = 1 instrução

5.for(int j=0; j < A.length-1; j++) { // 1 inicialização, n comparações e n-1 incrementos, 1 vez = 2n instruções

6.if(A[j] > A[j+1]) { // n-1 operações lógicas, 1 vez = n-1 instruções

7.troca(A, j, j+1); // nenhuma troca (o arranjo já está ordenado) = 0 instruções

8.trocou=true; // nenhuma troca (o arranjo já está ordenado) = 0 instruções

11.while(trocou==true); // 1 operação lógica (apenas 1 vez, por que o arranjo já está ordenado) = 1 instrução

Assim sendo, o somatório de suas instruções é igual a: 1 + 1 + 2n + (n-1) + 1. Ao reduzirmos essa expressão, temos que o algoritmo realiza um total de 3n+2 instruções. Dizemos que T(n)=3n+2 é a fórmula de complexidade de tempo desse algoritmo no melhor caso. Outro aspecto importante de se observar é que 3n+2 é uma função do 1º grau, portanto o Bubble Sort possui complexidade linear no melhor caso.

Resumindo:

  • No pior caso, o algoritmo possuirá complexidade quadrática: T(n)=5n2-n+1
  • No melhor caso, o algoritmo possuirá complexidade linear: T(n)=3n+2

Compartilhe este artigo

Share on whatsapp
WhatsApp
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on email
Email

Nos siga
em nossas redes sociais.