analise algoritmos recursivos parte 2

Prévia do material em texto

Mergesort
1
Mergesort
Fase de 
Divisão
Fase de 
Conquista
2
MergeSort	(A,	inicio,	fim)	
if	inicio	<	fim	then	
	 meio	←	⎣	(inicio	+	fim)/2	⎦ 
	 MergeSort(A,	inicio,	meio)	
	 MergeSort(A,	meio	+	1,	fim)	
	 Merge(A,	inicio,	meio,	fim)	
	
Mergesort
3
Θ(n)
Θ(1)
T(n) = O(1), se n = 1 
T(n) = 2T(n/2) + O(n)
Recorrência
Qual o custo?
4
5
1: T(n) = 2T(n/2) + n
T(n/2) = 2T(n/4) + n/2
2: T(n) = 2(2T(n/4) + n/2) + n
= 4T(n/4) + 2n
T(n/4) = 2T(n/8) + n/4
3: T(n) = 4(2T(n/8)+n/4) + 2n
= 8T(n/8) + 3n
k: T(n) = 2k T(n/2k) + kn
n/2k = 1 
k = lgn
T(n) = 2lgn T(n/2lgn) + nlgn 
= n + nlgn
O(nlgn)
Resolvendo por árvore de 
recursão
1. Construir a árvore de recursão 
2. Identificar custo de cada nível 
3. Achar uma relação no somatório dos níveis 
4. Calcular a altura da árvore 
5. Usar fórmula encontrada no passo 3 para somar o 
custo de todos os níveis
6
T(n)
7
8
Resolvendo por árvore de 
recursão
1. Construir a árvore de recursão 
2. Identificar custo de cada nível 
3. Achar uma relação no somatório dos níveis 
4. Calcular a altura da árvore 
5. Usar fórmula encontrada no passo 3 para somar o 
custo de todos os níveis
9
10
Resolvendo por árvore de 
recursão
1. Construir a árvore de recursão 
2. Identificar custo de cada nível 
3. Achar uma relação no somatório dos níveis 
4. Calcular a altura da árvore 
5. Usar fórmula encontrada no passo 3 para somar o 
custo de todos os níveis
11
12
níveis * Θ(n) 
Resolvendo por árvore de 
recursão
1. Construir a árvore de recursão 
2. Identificar custo de cada nível 
3. Achar uma relação no somatório dos níveis 
4. Calcular a altura da árvore 
5. Usar fórmula encontrada no passo 3 para somar o 
custo de todos os níveis
13
nível 0: n
nível 1: n/2
nível 2: n/4
...
nível i: n/2i
14
1 = n/2i 
n = 2i 
i = lgn
lgn + 1 níveis
Resolvendo por árvore de 
recursão
1. Construir a árvore de recursão 
2. Identificar custo de cada nível 
3. Achar uma relação no somatório dos níveis 
4. Calcular a altura da árvore 
5. Usar fórmula encontrada no passo 3 para somar o 
custo de todos os níveis
15
nível 0: n
nível 1: n/2
nível 2: n/4
...
nível i: n/2i
1 = n/2i
n = 2i
i = lgn
Altura: lgn
Níveis: lgn + 1
16
n * (lgn + 1) = nlgn + n = O(nlgn)