Baixe o app para aproveitar ainda mais
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
Compartilhar