AED Custo e Recursividade

Prévia do material em texto

ALGORITMOS E ESTRUTURAS DE DADOS 
EXERCÍCIOS RESOLVIDOS: CUSTO 
PROFESSOR: TIAGO A. E. FERREIRA 
ALUNA: ERICKA PRICILA DA SILVA 
BSI - 2016.2 
 
(1) SELECTION SORT 
 
*OBS 1: Na implementação do algoritmo abaixo, leve em conta que o índice do vetor começa 
em 1 e não em 0. 
 
Entrada:​ um vetor de tamanho (n) a ser ordenado. 
 
0 selectionSort​(​vetor ​) custos vezes 
1 n ​len​(​vetor ​)← c1 1 
2 for ​j 1 ​to​ ​n-1← c2 n 
3 menor j← c3 n-1 
4 for ​i j+1 to n← c4 n-j∑
n−1
j=1
 
5 if ​A[i] < A[menor] c5 n-j-1∑
n−1
j=1
 
6 menor i← c6 ∑
n−1
j=1
tj 
7 *​trocar(A[j],A[menor] c7 n-1 
 
Saída:​ o vetor ordenado. 
*OBS 2: esta linha representa uma função, a ​trocar()​. Ela recebe duas entradas que são posições 
de um determinado array a serem trocadas. 
 
ANALISANDO: ​Este código possui um ​loop invariante​(que é verdade sempre no ínicio, na 
manutenção e no final do código) no m ​que é o do subarranjo ​A[1…(j-1)] (que está ordenado 
de forma crescente) e ele vai consistir dos j-1 menores elementos do arranjo total ​A[1...n]​. Após 
as ​(n-1) ​iterações do laço ​for​(na linha 2), o subarranjo ​A[1…(n-1)] ​conterá os ​n-1 ​menores 
elementos do arranjo total que é o ​A[1…n], ​de forma ordenada e crescente. Isso implica que o 
elemento faltante, no caso o elemento ​A[n]​, terá que ser o maior elemento do arranjo. 
 
*OBS 3: ​existem alguns somatórios que são bastante utilizados, então é bom relembrar: 
 
 ​P. ARITMÉTICA P. GEOMÉTRICA QUADRADO INVERSOS 
 ∑
n
k=1
k = 2
n(n+1) ∑
n
k=0
x k = (x−1)
x −1 n +1 ∑
n
k=0
k 2 = 6
n(n+1)(2n+1) ln(n) O(1)∑
n
k=1
k
1 = + 
 
 
 
 
 
CALCULANDO OS CUSTOS: ​O​ ​Primeiro passo é abrir os somatórios que aparecerem: 
 
 (n ) n ) . . n ) ∑
n−1
j=1
n − j = − 1 + ( − 2 + . + ( − n + 1 = ∑
n−1
j=1
j = 2
n. (1 + (n−1)) = 2
 n 2 
 
 (n ) n ) . . n ) ∑
n−1
j=1
n − j − 1 = − 2 + ( − 3 + . + ( − n = ∑
n−2
j=0
j = 2
n. (0 + (n−2)) = 2
 n −2n 2 
 
Segundo passo é somar todos os custos: 
 
 
E por último realizar as análises de melhor e pior caso. Vamos primeiro ao ​melhor caso​, que 
seria pra = 0(em c6), ou seja, o arranjo já entrar ordenado: tj 
 
 
Como, de qualquer forma, teremos que percorrer o vetor exatamente ​(n) ​vezes (aqui, pra ser 
mais precisa, deveria ser ​(n+1)​, pois o laço vai até ​(n) e depois roda mais uma vez para 
confirmar a verificação, mas como é uma constante pequena, pude desprezar) ​para afirmar que 
a entrada está realmente ordenada, então no pior caso, temos que: 
 
MELHOR CASO:​ .(n) Θ (n )T = 2 
 
Vamos agora olha para o ​pior caso​, que aqui seria uma entrada ordenada de forma decrescente, 
ou seja, n j tj = − − 1 
 
Pelo mesmo motivo citado acima, temos o nosso pior caso com tempo: 
 
PIOR CASO:​ .(n) Θ (n )T = 2 
 
(2) FATORIAL 
Diferente do caso anterior, aqui vamos usar a abordagem dividir para conquistar e calcular o 
custo de um função que retorna o fatorial de um determinado número. 
 
Entrada​: número o qual, queremos saber o valor do fatorial 
 
0​ ​fatorial​( ​n​) 
1 if ​n == 0 (1), se n 0Θ = 
2 return ​1 (n) T 
3 else T( n-1) + , se n >0(1)Θ 
4 return ​n * ​fatorial​(n-1) 
 
Se seguirmos o raciocínio que a recursão nos acomete, teremos então, além do método da 
árvore: 
 
Logo, pelas regras do crescimento de funções assintóticas, temos que: 
 
 T(n) = (n+1). = ​ =​ (1)Θ ((n ) )Θ + 1 * 1 (n)Θ 
 
MAS essa não é uma prova formal! Sabemos que toda recursão tem seu caso base e sua regras 
para conduzir qualquer outro caso até seu caso base, então a relação de recursividade dessa 
função é dada por: 
 
T(0) = 1 
T(n) = T(n - 1) + 1 , ​Com isso, através da indução podemos supor que T(n) = n + 1 e começar a 
nossa prova. 
1)Passo Base: 
Para n = 0, chegamos ao resultado de T(0) = 1. OK! 
2)Passo Indutivo​: 
2.1) Hipótese Indutiva: ​Vamos supor que ​T(n) = n+1 ​seja verdade para qualquer 
constante positiva ​k ​. Desta forma, a nossa H.I fica sendo ​T(k) = k +1 
2.2) Tese Indutiva: ​Agora o ponto é prova que ​T(k+1) = k+2​. Utilizaremos a última 
relação indutiva que nos diz que: ​T(k+1) = T(k) + 1​, logo, substituindo ​k ​por ​k+1​, ficamos com: 
T(k+1) = ​k + 1 ​+ 1 = k + 2 como queríamos demonstrar(c.q.d).​ Sendo assim, conclui-se a→ 
prova indutiva de que T(n) = n + 1, portanto ​se​ T(n) = n + 1 ​então​ T(n) = .(n)Θ 
 
 
 
 
 
(3) INDUÇÃO E RECURSIVIDADE 
 
Enunciado: ​Use a indução matemática para mostrar que quando ​n ​é uma potência exata de 2 a 
solução da recorrência: 
 
é ​ ​T(n) = n.lg(n) 
 
 
Resposta: 
1) Passo Base: 
Antes de mais nada, é de extrema importância observar, que o caso base para o problema 
proposto, é ​n = 2​. Partindo daí, teremos então aplicando no que nos foi dado: 
n.lgn = (2). lg(2) 
= 2. 1 
 = 2 ​OK! 
2) Passo Indutivo: 
2.1)Hipótese Indutiva: ​Aqui teremos com hipótese: ( ) ).lg( ) T 2
n = ( 2
n
2
n 
2.2)Tese Indutiva: ​Aplicando a hipótese na relação de recorrência ​T(n) = 2.T + n​ ,)( 2
n 
conseguimos provar da seguinte forma: 
 
*OBS: ​É interessante ressaltar que a 
transformação da linha ​4 para ​5​, se dá 
devido a uma propriedade dos 
logaritmos que diz que: 
 
lg(a) lg(b) lg(b)
lg(a) = − 
 
Por isso que ​lg(n) /lg(2) ​se torna 
(lg(n) - lg(2))