Buscar

08 Aula 08 2

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

ANÁLISE DE ALGOTIMOS
Aula #
Kissema Eduardo Rafael
Instituto Superior Politécnico de Tecnologias e Ciências
Departamento de Engenharias e Tecnologias
19/09/2017
Sumário
} Divide e Conquista
} Teorema de Mestre
2
Divide e Conquista
} Divide e conquista é provavelmente a técnica geral de 
algoritmo mais conhecida. 
} Os algoritmos com estratégia divide e conquista seguem 
os seguintes passos:
1. A instância do problema é dividida em pequenas instâncias 
do problema (preferencialmente com o mesmo tamanho)
2. As instâncias pequenas do problemas são 
resolvidas(tipicamente recursivamente, alem de que, muitas 
vezes um algoritmo diferentes é empregado quando as 
instancias tornam-se muito pequenas)
3. Se necessário, as soluções obtidas para instancias pequenas 
do problema são combinadas para se obter solução original.
3
Divide e Conquista
} Consideremos o problema de cálculo
da soma de números a0, …, an–1. Se
n>1, podemos dividir o problema em
duas instâncias do mesmo problema:
} Calcular a soma dos primeiros ⎣1/2⎦ e do
restantes ⎡1/2⎤ números.
} Se n = 1, retornamos simplesmente a0
} Depois do calculo de cada soma podemos
adiciona-los para se obter a soma total:
a0+…+an–1 =(a0+ … +a⎣1/2⎦–1 )
+(a ⎣1/2⎦+ … +an–1 )
4
Problema de 
tamanho n
Subproblema
1de tamanho 
n/2
Subproblema
2de tamanho 
n/2
Solução do 
subproblema 1
Solução do 
subproblema 2
Solução do 
problema original
Divide e Conquista
} O exemplo do cálculo da soma ilustra o caso mais típico 
da estratégia divide e conquista: 
} um problema de tamanho n é dividido em duas instâncias de 
tamanho n/2. Mais genericamente, uma instância de tamanho n
pode ser dividido em várias instâncias de tamanho n/b, com a
delas precisando ser resolvido. (Aqui, a e b são constantes; a≥1 
e b>1). Assumindo que o tamanho n é uma potência de b, para 
simplificar nossa análise, temos a recorrência a seguir para o 
tempo de execução T(n):
T(n)=aT(n/b) + f(n) (4.1)
Onde f(n) é a função que conta o número de vezes que é 
efectuada a divisão do problema em pequenos problemas e a 
combinação das suas soluções.
5
Divide e Conquista
} Recorrência 4.1 é chamado de relação geral de divide e conquista.
Obviamente, a ordem de crescimento de sua solução T(n) depende dos
valores das constantes a e b e a ordem de crescimento da função f(n).
} A análise de eficiência dos algoritmos de tipo divide e conquista é
simplificada pelo seguinte algoritmo:
Teorema:
Se f(n)∈Θ(nd) onde d≥0 na equação de recorrência 4.1, então
Este resultado também é valido para as notações de O e Ω.
6
d
d
d
a
d
d
ba
ba
ba
Se
Se
Se
n
nn
n
nT
b >
=
<
⎪
⎩
⎪
⎨
⎧
Θ
Θ
Θ
∈
)(
)log(
)(
)(
log
Divide e Conquista
} Como por exemplo, a recorrência para o número de 
adições A(n) pelo algoritmo divide e conquista do cálculo 
da soma com tamanho de entrada n=2k é
A(n)=2A(n/2)+1
Assim, a=2, b=2 e d=0 então a>bd,
A(n)∈Θ(nlogba) = Θ(nlog22)=Θ(n).
7
Divide e Conquista
} Alguns Algoritmos de Divide e Conquista:
} Mergesort (ordenação interlação)
} Quicksort (Ordenação rápida)
} Busca binária
8
Exercícios
1. Resolva as seguintes relações de recorrências aplicando 
o teorema master.
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)
9

Outros materiais