Baixe o app para aproveitar ainda mais
Prévia do material em texto
25/03/2012 1 Prof. Debora Medeiros UTFPR – Universidade Tecnológica Federal do Paraná *Slides baseados no material do Prof. Thiago A. S. Pardo (USP) � Algoritmo está pronto/disponível � É importante determinar os recursos necessários ▪ Tempo ▪ Memória � Qual o principal quesito? Por que? 2 � Um algoritmo que soluciona um determinado problema � mas requer o processamento de um ano, não deve ser usado � O que dizer de uma afirmação como a abaixo? � “Desenvolvi um novo algoritmo chamado TripleX que leva 14,2 segundos para processar 1.000 números, enquanto o método SimpleX leva 42,1 segundos” ▪ Você trocaria o SimpleX que roda em sua empresa pelo TripleX? 3 � A afirmação tem que ser examinada, pois há diversos fatores envolvidos � Características da máquina em que o algoritmo foi testado ▪ Quantidade de memória � Linguagem de programação � Implementação pouco cuidadosa do algoritmo SimpleX vs. “super” implementação do algoritmo TripleX � Quantidade de dados processados ▪ Se o TripleX é mais rápido para processar 1.000 números, ele também é mais rápido para processar quantidades maiores de números, certo? 4 � Comparar algoritmos de forma independente de � Hardware � Linguagem de programação � Habilidade do programador � Comparar algoritmos e não programas � Área conhecida como “análise/complexidade de algoritmos” 5 � Sabe-se que � Processar 10.000 números leva mais tempo do que 1000 números � Cadastrar 10 pessoas em um sistema leva mais tempo do que cadastrar 5 � Etc. � Estimar a eficiência de um algoritmo em função do tamanho do problema � Assume-se que “n” é o tamanho do problema, ou número de elementos que serão processados � E calcula-se o número de operações que serão realizadas sobre os n elementos 6 25/03/2012 2 � O melhor algoritmo é aquele que requer menos operações sobre a entrada, pois é o mais rápido � O tempo de execução do algoritmo pode variar em diferentes máquinas, � mas o número de operações é uma boa medida de desempenho de um algoritmo � De que operações estamos falando? � Toda operação leva o mesmo tempo? 7 � TripleX � entrada de tamanho n ▪ n2+n operações � Pensando em termos de função: f(n)=n2+n � SimpleX � entrada de tamanho n ▪ 1.000n operações � g(n)=1.000n 8 � Faça os cálculos do desempenho de cada algoritmo para cada tamanho de entrada 9 Tamanho da entrada (n) 1 10 100 1.000 10.000 f(n)=n2+n g(n)=1.000n � Faça os cálculos do desempenho de cada algoritmo para cada tamanho de entrada � A partir de n=1.000, f(n) mantém-se maior e cada vez mais distante de g(n) � Diz-se que f(n) cresce mais rápido do que g(n) 10 Tamanho da entrada (n) 1 10 100 1.000 10.000 f(n)=n2+n 2 110 10.100 1.001.000 100.010.000 g(n)=1.000n 1.000 10.000 100.000 1.000.000 10.000.000 � Deve-se preocupar com a eficiência de algoritmos quando o tamanho de n for grande � comparar 2 algoritmos � determinar as taxas de crescimento de cada um � o algoritmo com menor taxa de crescimento rodará mais rápido quando o tamanho do problema for grande 11 � Notações que usaremos na análise de algoritmos � T(n) = O(f(n)) (lê-se big-oh, big-o ou “da ordem de”) se existirem constantes c e n0 tal que T(n) ≤ c * f(n) quando n ≥ n0 ▪ A taxa de crescimento de T(n) é menor ou igual à taxa de f(n) 12 25/03/2012 3 � Permite comparar a taxa de crescimento das funções correspondentes aos algoritmos � Não faz sentido comparar pontos isolados das funções, já que podem não corresponder ao comportamento assintótico 13 � Para 2 algoritmos quaisquer, considere as funções de eficiência correspondentes 1.000n e n2 � A primeira é maior do que a segunda para valores pequenos de n � A segunda cresce mais rapidamente e eventualmente será uma função maior, sendo que o ponto de mudança é n=1.000 � Existe uma constante c e um ponto n0 a partir do qual T(n) é menor ou igual a c*f(n) ▪ No nosso caso, T(n)=1.000n, f(n)=n2, c=1 e n0=1.000(ou, ainda, c=100 e n0=10) ▪ Dizemos que 1.000n=O(n2) 14 � As mais comuns 15 Função Nome c constante log n logarítmica log2n log quadrado n linear n log n n2 quadrática n3 cúbica 2n an exponencial 16 n tempo � Apesar de às vezes ser importante, não se costuma incluir constantes ou termos de menor ordem em taxas de crescimento � Queremos medir a taxa de crescimento da função ▪ torna os “termos menores” irrelevantes � As constantes também dependem do tempo exato de cada operação ▪ como ignoramos os custos reais das operações, ignoramos também as constantes � Não se diz que T(n) = O(2n2) ou que T(n) = O(n2+n) � Diz-se apenas T(n) = O(n2) 17 � Instruções simples � soma, multiplicação, comparação, atribuição, etc. � Por simplicidade e viabilidade da análise, assume-se que � cada instrução demora exatamente uma unidade de tempo para ser executada � Obviamente, em situações reais, isso pode não ser verdade: ▪ a leitura de um dado em disco pode demorar mais do que uma soma � Operações complexas, como inversão de matrizes e ordenação de valores, não são realizadas em uma única unidade de tempo, obviamente: devem ser analisadas em partes 18 25/03/2012 4 � Considera-se somente o algoritmo e suas entradas (de tamanho n) � Para uma entrada de tamanho n, pode-se calcular Tmelhor(n), Tmédia(n) e Tpior(n), ou seja, o melhor tempo de execução, o tempo médio e o pior, respectivamente � Obviamente, Tmelhor(n) ≤ Tmédia(n) ≤ Tpior(n) � Atenção: para mais de uma entrada, essas funções teriam mais de um argumento 19 � Geralmente, utiliza-se somente a análise do pior caso Tpior(n), pois ela fornece os limites para todas as entradas, incluindo particularmente as entradas ruins � Logicamente, muitas vezes, o tempo médio pode ser útil, principalmente em sistemas executados rotineiramente ▪ Por exemplo: em um sistema de cadastro de alunos como usuários de uma biblioteca, o trabalho difícil de cadastrar uma quantidade enorme de pessoas é feito somente uma vez; depois, cadastros são feitos de vez em quando apenas � Dá mais trabalho calcular o tempo médio � O melhor tempo não tem muita utilidade 20 � Supondo que as operações simples demoram uma unidade de tempo para executar, considere o programa abaixo para calcular o resultado de Início declare soma_parcial numérico; soma_parcial � 0; para i�1 até n faça soma_parcial�soma_parcial+i*i*i; escreva(soma_parcial); Fim 21 � Supondo que as operações simples demoram uma unidade de tempo para executar, considere o programa abaixo para calcular o resultado de Início declare soma_parcial numérico; soma_parcial � 0; para i�1 até n faça soma_parcial�soma_parcial+i*i*i; escreva(soma_parcial); Fim 22 1 unidade de tempo 4 unidades (1 da soma, 2 das multiplicações e 1 da atribuição) executada n vezes (pelo comando “para”) = 4n unidades 1 unidade para inicialização de i, n+1 unidades para testar se i≤n e n unidades para incrementar i = 2n+2 1 unidade para escrita � Supondo que as operações simples demoram uma unidade de tempo para executar, considere o programa abaixo para calcular o resultado de Início declare soma_parcial numérico; soma_parcial � 0; para i�1 até n faça soma_parcial�soma_parcial+i*i*i; escreva(soma_parcial); Fim 23 1 unidade de tempo 4 unidades (1 da soma, 2 das multiplicações e 1 da atribuição) executada n vezes (pelo comando “para”) = 4n unidades 1 unidade para inicialização de i, n+1 unidades para testar se i≤n e n unidades para incrementar i = 2n+2 1 unidade para escrita Custo total: somando tudo, tem-se 6n+4 unidades de tempo, ou seja, a função é O(n) � Ter que realizar todos esses passos paracada algoritmo (principalmente algoritmos grandes) pode se tornar uma tarefa cansativa � Em geral, como se dá a resposta em termos do big-oh, costuma-se desconsiderar as constantes e elementos menores dos cálculos � No exemplo anterior ▪ A linha soma_parcial�0 é insignificante em termos de tempo ▪ É desnecessário ficar contando 2, 3 ou 4 unidades de tempo na linha soma_parcial�soma_parcial+i*i*i ▪ O que realmente dá a grandeza de tempo desejada é a repetição na linha para i����1 até n faça 24 25/03/2012 5 � Repetições � O tempo de execução de uma repetição é pelo menos o tempo dos comandos dentro da repetição (incluindo testes) vezes o número de vezes que é executada 25 � Repetições aninhadas � A análise é feita de dentro para fora � O tempo total de comandos dentro de um grupo de repetições aninhadas é o tempo de execução dos comandos multiplicado pelo produto do tamanho de todas as repetições � O exemplo abaixo é O(n2) para i�0 até n faça para j�0 até n faça faça k�k+1; 26 � Comandos consecutivos � É a soma dos tempos de cada um, o que pode significar o máximo entre eles � O exemplo abaixo é O(n2), apesar da primeira repetição ser O(n) para i�0 até n faça k�0; para i�0 até n faça para j�0 até n faça faça k�k+1; 27 � Se... então... senão � Para uma cláusula condicional, o tempo de execução nunca é maior do que o tempo do teste mais o tempo do maior entre os comandos relativos ao então e os comandos relativos ao senão � O exemplo abaixo é O(n) se i<j então i�i+1 senão para k�1 até n faça i�i*k; 28 29 MAX(A) max � A[1] for i � 2 to n //n=|A| if max < A[i] max � A[i] return max MAX(A) max � A[1] for i � 2 to n //n=|A| if max < A[i] max � A[i] return max � n-1 comparações 30 25/03/2012 6 MAX(A) max � A[1] for i � 2 to n //n=|A| if max < A[i] max � A[i] return max � n-1 comparações � O(n) 31 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE 32 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : 33 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) 34 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: 35 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: � 1 comparação: O(1) 36 25/03/2012 7 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: � 1 comparação: O(1) � Caso médio: 37 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: � 1 comparação: O(1) � Caso médio: � 1p1 + 2p2 + … + npn 38 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: � 1 comparação: O(1) � Caso médio: � 1p1 + 2p2 + … + npn � Assumir pi = 1/n 39 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: � 1 comparação: O(1) � Caso médio: � 1p1 + 2p2 + … + npn � Assumir pi = 1/n � 1/n(1 + 2 + … + n) //PA 40 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: � 1 comparação: O(1) � Caso médio: � 1p1 + 2p2 + … + npn � Assumir pi = 1/n � 1/n(1 + 2 + … + n) //PA =(1+n)n/2n = (n+1)/2 41 BUSCA_SEQ(A,val) for i � 1 to n //n=|A| if A[i] = val return i return FALSE � Pior caso : � n comparações: O(n) � Melhor caso: � 1 comparação: O(1) � Caso médio: � 1p1 + 2p2 + … + npn � Assumir pi = 1/n � 1/n(1 + 2 + … + n) //PA =(1+n)n/2n = (n+1)/2 � O(n) 42 25/03/2012 8 � Chamadas a sub-rotinas � Uma sub-rotina deve ser analisada primeiro e depois ter suas unidades de tempo incorporadas ao programa/sub-rotina que a chamou 43 � Sub-rotinas recursivas � Se a recursão é um “disfarce” da repetição (e, portanto, a recursão está mal empregada, em geral), basta analisá-la como tal � O exemplo é obviamente O(n) 44 sub-rotina fatorial(n: numérico) início declare aux numérico; se n≤1 então aux�1 senão aux�n*fatorial(n-1); retorne aux; fim Eliminando a recursão sub-rotina fatorial(n: numérico) início declare aux numérico; aux�1; enquanto n>1 faça aux�aux*n; n�n-1; retorne aux; fim � Sub-rotinas recursivas � Em muitos casos ▪ (incluindo casos em que a recursividade é bem empregada) ▪ é difícil transformá-la em repetição ▪ Solução: análise de recorrência ▪ Recorrência: equação ou desigualdade que descreve uma função em termos de seu valor em entradas menores ▪ Caso típico: algoritmos de dividir-e-conquistar ▪ desmembram o problema em vários subproblemas � semelhantes ao problema original, mas menores em tamanho, ▪ resolvem os subproblemas recursivamente ▪ combinam essas soluções criando uma solução para o problema original ▪ Exemplos? 45 � Exemplo: potência de um número Início declare ac, a, i e n numéricos; ler a e n; ac�1; i�0; enquanto i<n faça ac�ac*a; i�i+1; Fim 46 sub-rotina potencia(a: numérico, n: numérico) início declare aux numérico; se n=1 retorne (a) se n é par aux�potencia(a,n/2) retorne(aux*aux) senão aux�potencia(a,(n-1)/2); retorne (aux*aux*a) fim � Alguns métodos para resolver recorrências � Método da substituição � Método da árvore de recursão � Método mestre 47 � Alguns métodos para resolver recorrências � Método da substituição � Método da árvore de recursão � Método mestre 48 25/03/2012 9 � Método da árvore de recursão � Esboça-se uma árvore que, nível a nível, representa as recursões sendo chamadas � Em seguida, em cada nível/nó da árvore, são acumulados os tempos necessários para o processamento ▪ No final, tem-se a estimativa de tempo do problema 49 � T(n)=aT(n/b)+f(n) ▪ a: número de subproblemas ▪ n/b: tamanho do subproblema ▪ f(n): trabalho independente da recursão 50 ▪ a: 1 (subproblema) ▪ b: n/2 (tamanho do subproblema) ▪ T(n) = 1T(n/2) + O(1) 51 � Árvore de recursão ▪ T(n) = 1T(n/2) + c 52 T(n) � Árvore de recursão ▪ T(n) = 1T(n/2) + c 53 c T(n/2) � Árvore de recursão ▪ T(n) = 1T(n/2) + c 54 c c T(n/4) 25/03/2012 10 � Árvore de recursão ▪ T(n) = 1T(n/2) + c 55 c c c O(1) � Árvore de recursão ▪ T(n) = 1T(n/2) + c 56 c c c h=lg n O(1) � Árvore de recursão ▪ T(n) = 1T(n/2) + c 57 c c c h=lg n Total = O(lgn) O(1) � A análise assintótica é uma ferramenta fundamental ao projeto, análise ou escolha de um algoritmo específico para uma dada aplicação � No entanto, deve-se ter sempre em mente que essa análise “esconde” fatores assintoticamente irrelevantes, mas que em alguns casos podem ser relevantes na prática, particularmente se o problema de interesse se limitar a entradas (relativamente) pequenas � Por exemplo, um algoritmo com tempo de execução da ordem de 10100n é O(n), assintoticamente melhor do que outro com tempo 10 n log n, o que nos faria, em princípio, preferir o primeiro � No entanto, 10100 é o número estimado por alguns astrônomos como um limite superior para a quantidade de átomos existente no universo observável! 58 59 � Estime quantas unidades de tempo são necessárias para rodar o algoritmo abaixo Início declare i e j numéricos; declare Avetor numérico de n posições; i�1; enquanto i≤n faça A[i]�0; i�i+1; para i�1 até n faça para j�1 até n faça A[i]�A[i]+i+j; Fim
Compartilhar