Análise de algoritmo

Prévia do material em texto

Análise de algoritmo – Atividade A3.
-
Pesquise e apresente um algoritmo com recorrência, cuja complexidade pode ser resolvida por indução matemática, pelo método da substituição ou por árvore de recursão. 
Pontuação: a) Apresentação do algoritmo com sua equação de complexidade T(n), (5,0 pontos); 
Utilizei para realizar esta tarefa o algoritmo de Pesquisa Binária em linguagem C. Conforme a seguir nos comentário do código tem explicando o código como que a busca de uma árvore. 
int Search (int vet[], int key, int size)
{
 int inf = 0; // limite inferior (o primeiro índice de vetor em C é zero )
 int sup = size-1; // limite superior (termina em um número a menos. 0 a 9 são 10 números)
 int meio;
 while (inf <= sup)
 {
 meio = (inf + sup)/2;
 if (key== vet[meio])
 return meio;
 if (key < vet[meio])
 sup = meio-1;
 else
 inf = meio+1;
 }
 return -1; // não encontrado
}
//Implementação Recursiva:
// n => chave | v[] => vetor ordenado | e => limite inferior (esquerda) | d => limite superior (direita)
int Search(int n, int v[], int e, int d)
{
 int meio = (e + d)/2;
 if (v[meio] == n)
 return meio;
 if (e >= d)
 return -1; // não encontrado
 else
 if (v[meio] < n)
 return Search(n, v, meio+1, d);
 else
 return Search(n, v, e, meio-1);
}
b) Resolvendo sua complexidade por um dos três métodos supracitados (5,0 pontos).
T(n) = 2T(n/2) + n
 = 2(2T(n/4) + n/2) + n = 4T(n/4) + n + n = 4T(n/4) + 2n
 = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + n + 2n = 8T(n/8) + 3n
 = 8(2T(n/16) + n/8)+ 3n = 8T(n/16)+ n + 3n = 16T(n/16) + 4n
 ... = 32T(n/32) + 5n
 ...
 = n*T(1) + log2(n)*n
 = O(n*log2(n))
Onde: