Analise de Algoritmos - Recorrências e Complexidade

Análise de Algoritmos Rogério Güths Aula Recorrências aplicação Recorrências Vimos o que é uma Recorrência Vimos como resolvêla obtendo uma fórmula direta limitante superior Dissemos que é útil para analisar o consumo de tempo de algoritmos recursivos Recorrências Vimos o que é uma Recorrência Vimos como resolvêla obtendo uma fórmula direta limitante superior Dissemos que é útil para analisar o consumo de tempo de algoritmos recursivos Mas como faremos esta utilização Como relacionamos um Algoritmo e uma Recorrência Complexidade Algoritmo não recursivo Analise o algoritmo ao lado Quantas operações ele realiza para um vetor de tamanho n void positivoNegint tamanho int vetor int positivos negativos positivos 0 negativos 0 printfComeçar a verificar os números fori0itamanhoi ifvetori0 printfNumero negativo negativos else printfNumero positivo positivos printfTotal i positivos e i negativos positivos negativos Algoritmo não recursivo Como ele não é recursivo basta identificarmos quantas execuções ocorrem Em cada linha No pior caso E somar tudo void positivoNegint tamanho int vetor int positivos negativos positivos 0 negativos 0 printfComeçar a verificar os números fori0itamanhoi ifvetori0 printfNumero negativo negativos else printfNumero positivo positivos printfTotal i positivos e i negativos positivos negativos Algoritmo não recursivo Algo do tipo void positivoNegint tamanho int vetor int positivos negativos positivos 0 negativos 0 printfComeçar a verificar os números fori0itamanhoi ifvetori0 printfNumero negativo negativos else printfNumero positivo positivos printfTotal i positivos e i negativos positivos negativos 1 1 1 Algoritmo não recursivo Porém observando que os laços tem um efeito multiplicativo sobre seu interior void positivoNegint tamanho int vetor int positivos negativos positivos 0 negativos 0 printfComeçar a verificar os números fori0itamanhoi ifvetori0 printfNumero negativo negativos else printfNumero positivo positivos printfTotal i positivos e i negativos positivos negativos 1 1 1 n Algoritmo não recursivo Também analisando execuções ou não de ifs no pior caso void positivoNegint tamanho int vetor int positivos negativos positivos 0 negativos 0 printfComeçar a verificar os números fori0itamanhoi ifvetori0 printfNumero negativo negativos else printfNumero positivo positivos printfTotal i positivos e i negativos positivos negativos 1 1 1 n 3 Algoritmo não recursivo Totalizando void positivoNegint tamanho int vetor int positivos negativos positivos 0 negativos 0 printfComeçar a verificar os números fori0itamanhoi ifvetori0 printfNumero negativo negativos else printfNumero positivo positivos printfTotal i positivos e i negativos positivos negativos 1 1 1 n 3 1 111n31 3n4 Algoritmo não recursivo É óbvio que esta análise pode se complicar com utilização intensa de ifs laços condicionais e chamadas de subrotinas Mas utilizando o argumento de se tratar do Pior Caso e fazendo arredondamentos para cima não é difícil a obtenção de um bom limitante superior Além disso como o objetivo é obter O as constantes podem ser majoradas sem prejuízo do resultado final em termos da classe de complexidade void positivoNegint tamanho int vetor int positivos negativos positivos 0 negativos 0 printfComeçar a verificar os números fori0itamanhoi ifvetori0 printfNumero negativo negativos else printfNumero positivo positivos printfTotal i positivos e i negativos positivos negativos 1 11 n 3 1 3n4 On Complexidade Algoritmo recursivo Analise o algoritmo ao lado Quantas operações ele realiza para um vetor de tamanho n int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Algoritmo recursivo Agora a situação muda bastante Como calcular a quantidade de operações nestas linhas int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Algoritmo recursivo Agora a situação muda bastante Como calcular a quantidade de operações nestas linhas Não existe uma fórmula direta É ai que entra a Recorrência int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Algoritmo recursivo É ai que entra a Recorrência int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Tn2 Tn2 Algoritmo recursivo Vejamos como fica completando as linhas int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Tn2 Tn2 1 2 1 1 Algoritmo recursivo Repare que agora podemos separar em T1 quando tamanho da entrada é 1 Tn quando tamanho da entrada é 1 int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Tn2 Tn2 1 2 1 1 Algoritmo recursivo Repare que agora podemos separar em T1 quando tamanho da entrada é 1 Tn quando tamanho da entrada é 1 T1 ocorre quando fiminicio T1 1214 int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Tn2 Tn2 1 2 1 1 Algoritmo recursivo Repare que agora podemos separar em T1 4 Tn quando tamanho da entrada é 1 Tn ocorre quando fiminicio executa else Tn 11Tn2Tn21 2Tn23 int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Tn2 Tn2 1 2 1 1 Algoritmo recursivo Então temos T1 4 Tn 2Tn23 Dá para obtermos um bom limitante superior int positivoint inicio int fim int Tposit int meio iffiminicio ifvetorinicio0 printfNumero negativo Tposit 0 else printfNumero positivo Tposit 1 else meio fiminicio2 inicio Tposit positivoinicio meio Tposit Tposit positivomeio fim printfPositivos até o momentoiTposit return Tposit Tn2 Tn2 1 2 1 1 Algoritmo recursivo Exercício Obtenha a Recorrência e um bom limitante superior para o algoritmo ao lado int maiorint inicio int fim int Maximo int Terco int Temp iffiminicio Maximo vetorinicio else Terco fiminicio3 Maximo maiorinicio inicioterco Temp maiorinicioterco inicio2terco ifTemp Maximo Maximo Temp Temp maiorinicio2tercofim ifTemp Maximo Maximo Temp printfMaior até o momentoiMaximo return Maximo