AEDSII_aula_007_analise_de_algoritmos

Prévia do material em texto

Algoritmos e Estrutura de Dados II 
Técnicas de Análise de Algoritmos 
n  Determinar o tempo de execução de um programa 
pode ser um problema matemático complexo; 
n  Determinar a ordem do tempo de execução, sem 
preocupação com o valor da constante envolvida, 
pode ser uma tarefa mais simples. 
q  manipulação de somas 
q  produtos, 
q  permutações, 
q  fatoriais, 
q  coeficientes binomiais, 
q  solução de equações de recorrência 
 
Algoritmos e Estrutura de Dados II 
Análise do Tempo de Execução 
n  Comando de atribuição, de leitura ou de escrita: O(1). 
 
int a; 
int v[15]; 
 
 a = 0; 
 v[0] = 12; 
Algoritmos e Estrutura de Dados II 
Análise do Tempo de Execução 
n  Sequencia de comandos: 
n  Determinado pelo maior tempo de execução de qualquer 
comando da sequencia. 
 
sum = 0; 
for (i = 0; i < sqrt(n)/2; i++) 
 sum++; 
for (j = 0; j < sqrt(n)/4; j++) 
 sum++; 
for (k = 0; k < 8+j; k++) 
 sum++; 
Algoritmos e Estrutura de Dados II 
Análise do Tempo de Execução 
n  Comando de decisão: 
n  Tempo dos comandos dentro do condicional, mais tempo para 
avaliar a condição, que é O(1). 
 
if ( A[j] < A[min] )‏ 
 min = j; 
 
Algoritmos e Estrutura de Dados II 
Análise do Tempo de Execução 
n  Laço: 
n  Soma do tempo de execução do corpo do laço + o tempo de 
avaliar a condição de parada (geralmente O(1)) X número de 
iterações. 
 
sum = 0; 
 
for (i = 0; i < sqrt(n)/2; i++) { 
 if ( A[j] < A[min] )‏ 
 min = j; 
 sum++; 
} 
Algoritmos e Estrutura de Dados II 
Análise do Tempo de Execução 
n  Procedimentos não recursivos: 
n  Cada um deve ser computado separadamente, iniciando pelos que 
não chamam outros procedimentos. Avalia-se então os que são 
chamam os já avaliados (utilizando os tempos desses). 
n  O processo é repetido até chegar no programa principal. 
 
Algoritmos e Estrutura de Dados II 
Exemplo 1 
void exemplo1 (int n) 
{ 
 int i, a; 
 a=0; 
 for (i = 0; i < n; i++) 
 a += i; 
} 
Qual a Função de Complexidade para o 
número de atribuições à variável a? 
Qual a Ordem de Complexidade da 
função exemplo1 ? 
Algoritmos e Estrutura de Dados II 
Exemplo 2 
void exemplo2 (int n) 
{ 
 int i, j, a; 
 a = 0; 
 for (i = 0; i < n; i++) 
 for (j = n; j > i; j--) 
 a += i + j; 
 exemplo1(n); 
} 
Algoritmos e Estrutura de Dados II 
Exemplo 
Algoritmo de Ordenação 
n  Seleciona o menor elemento do conjunto. 
n  Troca este com o primeiro elemento A[0]. 
n  Repita as duas operações acima com os n - 1 elementos 
restantes, depois com os n - 2, até que reste apenas um. 
Algoritmos e Estrutura de Dados II 
Procedimento não Recursivo 
Algoritmo para ordenar os n elementos de um conjunto A em ordem ascendente. 
 
 
 
 ‏)1(
 ‏)2(
 ‏)3(
 ‏)4(
 ‏)5(
 
 ‏)6(
 ‏)7(
 ‏)8(
 
void Ordena(int* A, int n) ‏ 
{ /*ordena o vetor A em ordem ascendente*/ 
 int i, j, min,x; 
 for (i = 0; i < n-1; i++) 
 { min = i; 
 for (j = i; j < n; j++) 
 if ( A[j] < A[min] )‏ 
 min = j; 
 /* troca A[min] e A[i] */ 
 x = A[min]; 
 A[min] = A[i]; 
 A[i] = x; 
 } 
} 
 
Qual a complexidade 
em termos do 
número de 
comparações com 
elementos de A? 
Algoritmos e Estrutura de Dados II 
Procedimento não Recursivo 
 
 
 
 ‏)1(
 ‏)2(
 ‏)3(
 ‏)4(
 ‏)5(
 
 ‏)6(
 ‏)7(
 ‏)8(
 
void Ordena(int* A, int n) ‏ 
{ 
 int i, j, min,x; 
 for (i = 0; i < n-1; i++) 
 { min = i; 
 for (j = i; j < n; j++) 
 if ( A[j] < A[min] )‏ 
 min = j; 
 /* troca A[min] e A[i] */ 
 x = A[min]; 
 A[min] = A[i]; 
 A[i] = x; 
 } 
} 
Laço Interno 
n  Contém um comando de decisão, com 
um comando de atribuição (tempo 
constante). 
n  Quanto ao corpo do comando de decisão, 
devemos considerar o pior caso, 
assumindo que será sempre executado. 
n  O tempo para incrementar o índice do 
laço e avaliar a condição de terminação é 
O(1). 
n  O tempo combinado para executar uma 
vez o laço é O(max(1, 1, 1)) = O(1), 
conforme regra da soma para a notação 
O 
n  Como o número de iterações é n - i, o 
tempo gasto no laço é O((n - i) x 1) = O(n 
- i), conforme regra do produto para a 
notação O. 
Algoritmos e Estrutura de Dados II 
Procedimento não Recursivo 
 
 
 
 ‏)1(
 ‏)2(
 ‏)3(
 ‏)4(
 ‏)5(
 
 ‏)6(
 ‏)7(
 ‏)8(
 
void Ordena(int* A, int n) ‏ 
{ 
 int i, j, min,x; 
 for (i = 0; i < n-1; i++) 
 { min = i; 
 for (j = i; j < n; j++) 
 if ( A[j] < A[min] )‏ 
 min = j; 
 /* troca A[min] e A[i] */ 
 x = A[min]; 
 A[min] = A[i]; 
 A[i] = x; 
 } 
} 
Laço Externo 
n  Contém, além do laço interno, quatro 
comandos de atribuição. 
O(max(1, (n - i), 1, 1, 1)) = O(n - i). 
n  A linha (1) é executada n - 1 vezes, e o 
tempo total para executar o programa 
está limitado ao produto de uma 
constante pelo somatório de (n - i): 
 
 
n  Se considerarmos o número de 
comparações como a medida de custo 
relevante, o programa faz (n2)/2 - n/2 
comparações para ordenar n elementos. 
n  Se considerarmos o número de trocas, o 
programa realiza exatamente n - 1 trocas. 
Algoritmos e Estrutura de Dados II 
Exercício 1 
// Considere A, B e C vetores globais 
 
void p1 (int n) 
{ 
 int i, j, k; 
 
 for (i=0; i<n; i++) 
 for (j=0; j<n; j++) 
 { 
 C[i][j]=0; 
 for (k=n-1; k>=0; k--) 
 C[i][j]=C[i][j]+A[i][k]*B[k][j]; 
 } 
} 
O que faz essa função ? Qual 
a sua ordem de complexidade? 
Algoritmos e Estrutura de Dados II 
Exercício 2 
void p2 (int n) 
{ 
 int i, j, x, y; 
 
 x = y = 0; 
 for (i = 1; i <= n; i++) { 
 for (j = i; j <= n; j++) 
 x = x + 1; 
 for (j = 1; j < i; j++) 
 y = y + 1; 
 } 
} 
Qual a ordem de complexidade 
da função p2? 
Algoritmos e Estrutura de Dados II 
Exercício 3 
 
void Exercicio3(n){ 
 int i, j, a; 
 
 for (i=0; i<n; i++){ 
 if (x[i] > 10) 
 for (j=i+1; j<n; j++) 
 x[j] = x[j] + 2; 
 else 
 x[i] = 1; 
 j = n-1; 
 while (j >= 0) { 
 x[j] = x[j] - 2; 
 j = j - 1; 
 } 
 } 
} 
 
Qual a Função de Complexidade 
para o número de atribuições 
ao vetor x?