06 Aula 06

Prévia do material em texto

ANÁLISE DE ALGOTIMOS
Aula #06
Kissema Eduardo Rafael
Instituto Superior Politécnico de Tecnologias e Ciências
Departamento de Engenharias e Tecnologias
19/09/2017
Sumário
} Revisão Geral 
} Exercícios 
} Análise de Algoritmo Não Recursivos
} Análise de Algoritmo Recursivo
2
Revisão Geral
} Conceitos
3
Exercício #1
Algoritimo secreto(n)
//Introduz : um por um + 1 Matriz A[0..n-1, 0..n-1] numero reais
minval ← A[0]; 
maxval ← A[0];
for i ← 0 to n-2 do
for j ← i+1 to n-1 do
for k ← i to n do
A[j,k]← A[j,k]- A[i,k]* A[j,i]/ A[i,i]
Fim
4
Exercício #1
Algoritmo F(n)
//calcula n! recursivamente
Inicio
Se n=0 
retorna 1
Senão
retorna F(n – 1) * n
Fim
5
Exercício #1
Algoritmo BinRec(n)
Var n: inteiro
Inicio
Se n = 1 retorna 1
Senão retorna BinRec(⎣n/2⎦) + 1
Fim
6
Exercício #1
1. Resolva as seguintes relações de recorrências
a. X(n) = x(n – 1) + 5 para n>1 , x(1)=0
b. X(n) = 3x(n – 1) para n>1, x(1) = 4
c. X(n) = x(n – 1) + n para n > 0, x(0) = 0
d. X(n) = x(n/2) + n para n>1, x(1) = 1 (sabe-se que n = 2k)
e. X(n) = x(n/3) + 1 para n>1, x(1) = 1 (sabe-se que n = 3k)
7