Baixe o app para aproveitar ainda mais
Prévia do material em texto
FUNDAMENTOS DA ANÁLISE DA EFICIÊNCIA DO ALGORITMO Capítulo II Análise de algorítimo Assuntos: ◦ Correcto (exatidão), ◦ Eficiência de tempo, ◦ Eficiência de espaço ◦ Optimização Abordagens: ◦ análise teórica ◦ análise empírica Análise teórica da eficiência de tempo A eficiência do tempo é analisada através da determinação do número de repetições da operação básica do algoritmo em função do tamanho da entrada. tamanho de entrada tempo de execução tempo de execução para a operação básica nº de vezes que a operação básica é executada Nota: Entrada: ◦ Dados fornecidos Tamanho de entrada ◦ pode ser dado como número de valores num vector, o número de registos num ficheiro, enfim, um certo número de elementos que constituem a entrada de dados para o algoritmo. De modo que o tempo de execução de um algoritmo pode ser dado como uma função T(n) do tamanho n da sua entrada. Operação básica: ◦ a operação que mais contribui para o tempo de execução do algoritmo. Exemplos de tamanho da entrada e operação básica Problema medida de tamanho da entrada Operação Básica busca de chave em uma lista de n itens número de itens da lista, i. e. n comparação de chave Multiplicação de duas matrizes A dimensão da matriz ou o nº total dos elementos Multiplicação de dois números problema de grafo típico Nº de vértice e/ou arcos Visita a vértice ou travessia nos arcos. Análise empírica de eficiência de tempo Selecciona uma amostra específica (típico) de entradas Use unidade física de tempo (por exemplo, milissegundos) ou Contar número real de execuções da operação básica Analisar os dados empíricos Melhor-caso, Caso médio e Pior-caso Para alguns algoritmos eficiência depende de dados fornecidos: Pior caso: Cpior(n) – máximo sobre as entradas de tamanho n Melhor caso: Cmelhor(n) – mínimo sobre as entradas de tamanho n Caso médio: Cmedio(n) – "Média" com entradas de tamanho n ◦ Número de vezes que a operação básica será executada na entrada típica. ◦ Não a média de pior e melhor casos. ◦ Número esperado de operações básicas consideradas como uma variável aleatória sob alguma suposição sobre a distribuição de probabilidade de todas as entradas possíveis Casos de Eficiências Anteriormente vimos que era importante analisar a eficiência de algoritmos como sendo uma função de parâmetro n, o tamanho de entrada. Existem muitos algoritmos que o seu tempo de execução depende não só do tamanho da entrada mas sim, um especifico valor de entrada. Ex: Considere o algoritmo de busca sequencial abaixo alg 1.0 Claramente, o tempo de execução do algoritmo pode ser diferente para lista A[n] para mesma entrada n. Algoritmo BuscaSequencial (A[0.. n–1], K) // pesquisa um certo valor num dado vector usando busca sequencial // Entrada: O vector A[0.. n–1] e a chave de busca K // Saida: o indice do primeiro elemento de A iguail a chave K ou –1 se não for // encontrado elemento igual a chave K i <– 0 enquanto i <n E A[i] <> K faça i < - i + 1 Se i < n retorna i Senão retorna –1 Casos de eficiência Como se pode observar no algoritmo anterior, o tempo de execução do algoritmo pode ser diferente para o mesmo tamanho da lista. Pior caso É o método mais fácil de se obter. Baseia-se no maior tempo de execução sobre todas as entradas de tamanho n. No algoritmo anterior, pode-se observar que o pior caso, acontece quando o elemento a pesquisar não existir ou se o mesmo se encontrar na última posição, o algoritmo faz todas comparações possíveis para todos valores de entrada de tamanho n: Cpior(n)=n. Melhor Caso É o menor tempo de execução em uma entrada de tamanho n. Podemos analisar eficiencia do melhor caso como seguinte: ◦ Determinamos o valor do tamanho da entrada em que o contador C(n) é o menor para todos valores entrada de tamanho n. Isso, não quer dizer que o melhor caso seja o menor valor de n, isto é., para tamanho de entrada n o algoritmo executa mais rápido. No exemplo anterior, Cmelhor (n) = 1 Caso Médio Consideremos o caso do algoritmo da pesquisa sequencial alg1.0: ◦ A probabilidade de uma busca com sucesso é igual p onde 0<p<1 ◦ A probabilidade de sucesso ocorrer na i-ésima posição da lista é igual para cada i. ◦ No caso da busca com sucesso, a probabilidade de sucesso ocorrer na i-ésima posição da lista é n/p para cada i e o número de comparações feitas pelo algoritmo nesta situação é obviamente i. ◦ No caso de insucesso, o número de comparações é n com a probabilidade de (1 – p), assim: Caso Médio Cmed(n) =[1(p/n) + 2 (p/n) + … + i(p/n) + … + n(p/n)] + n(1 – p) =(p/n)[1 + 2 + … + i + … +n] + n(1 – p) =(p/n)[n(n + 1)/2] + n(1 – p) =p(n+1)/2 + n(1 – p) Se p = 1 (sucesso) o número de comparações é (n+1)/2 Se p = 0 (insucesso) – o número de comparações é n. Formulas para contagem de operação básica Fórmula Exacta C(n) = n(n–1)/2 Fórmula que indica a ordem de crescimento com a constante multiplicativa específica C(n) ≈ 0.5n2 Fórmula que indica a ordem de crescimento com constante multiplicativa desconhecida. C(n) ≈ c n2 Ordem de Crescimento Ordem de crescimento numa constante multipla quando n→∞ Exemplo: ◦ Quanto mais rápido o algoritmo será executado no computador que é duas vezes mais rápido? ◦ Quanto tempo demora para resolver o problema de dobro tamanho de entrada? Valores de algumas funções importantes quando n → ∞ n log2 n n n log2 n n 2 n3 2n n! 101 3,3 101 3,3*101 102 103 103 3,6*106 102 6,6 102 6,6*102 104 106 1,3*1030 9,3*10157 103 10 103 1,0*103 106 109 104 13 104 1,3*104 108 1012 105 17 105 1,7*105 1010 1015 106 20 106 2,0*106 1012 1018 Valores (alguns aproximado) de várias funções importantes para a análise de algoritmos. Notação assintótica Na sessão anterior, a análise da eficiência concentrou-se na ordem de crescimento da contagem de operação básica do algoritmo como principal indicador da eficiência do algoritmo. Para comparar e eleger essas ordens de crescimento, usamos as seguintes notações: O(big oh ), (big omega), (big theta) Ordem assintótica de crescimento Uma maneira de comparar as funções que ignora factores constantes e pequenos tamanhos de entrada O(g(n)): classe de funções f(n), que não crescem mais rápido que g(n) Θ(g(n)): classe de funções f(n), que crescem a mesma ordem que g(n) (g(n)): classe de funções f(n), que crescem, pelo menos, tão rápido quanto g(n) Notação Informal (Big Oh) O(g(n)) é um conjunto de todas funções com orden de crescimento menor ou igual que g(n) (para múltiplos de uma constante quando n tende a infinito) Ex.: nO(n2), 100n + 5 O(n2), (½)n(n–1) O(n2). n3O(n2), 0,00001n3O(n2), n4 +n + 1 O(n2). Notação Informal (big Omega) (g(n)) é um conjunto de todas funções com ordem de crescimento maior ou igual que g(n). Ex. n3 (n2), ½ n(n–1) (n2) mas 100n +5 (n2). Notação Informal (Big tetha) (g(n)) é um conjunto de todas funções que tem a mesma ordem de crescimento que g(n). Exemplo n3 (n3), ½ n(n–1) (n2) mas 100n +5 (n2). Notação Definição: A função f(n)O(g(n)), se e somente se existe uma constante positiva c e um inteiro não negativo n0 para todo positivo n, tal que: f(n)cg(n) para todo nn0 Ex. 100n+5 O(n2). Prova: 100n+5 100n +n ( n5) = 101n 101n2 Pondo c = 101 e n0= 5, temos 100n+5 O(n 2) Big-oh (O) cg(n)f(n) não importa Fig. 2.1 A notação Big-oh f(n) O(g(n)) Notação Definição: A função f(n)(g(n)), se e somente se existe uma constante positiva c e um inteiro não negativo n0 para todo positivo n, tal que: f(n) cg(n) para todo nn0 Ex. n3 (n2). Prova: n3n2 para todo n 0, Portanto podemos seleccionar c=1 e n0=0. Big-omega () cg(n) f(n) não importa Fig. 2.2A notação Big-omega f(n) (g(n)) Notação Definição A função f(n)(g(n)), se e somente se existe uma constantes positiva c1 e c2 e um inteiro não negativo n0 para todo positivo n, tal que: c1g(n) f(n)c2g(n) para todo nn0 Big-theta () c1g(n) f(n) não importa Fig. 2.3 A notação Big-theta f(n) (g(n)) c2g(n) Exemplo (½)n(n-1)(n2) (½)n(n-1) = (½)n2 – (½)n (1/2)n2 para todo n 0 (½)n(n-1)=(1/2)n2 – (1/2)n ½)n2 – (½)n * (½)n para todo n 2 =(¼) n2 Logo, pode-se seleccionar c2=¼ , c1=½ e n0=2 Propriedades 1. f(n) ∈ O(f(n)) 2. f(n) ∈ O(g(n)) sse g(n) ∈(f(n)) 3. Se f(n) ∈ O(g(n)) e g(n)∈O(h(n)), então f(n) ∈O(h(n)) Nota semelhança com a ≤ b 1. Se f1(n) ∈ O(g1(n)) e f2(n) ∈ O(g2(n)) , então f1(n) + f2(n) ∈ O(max{g1(n), g2(n)}) Ordem de crescimento usando limites As definições de , e indispensáveis para demonstração das propriedades abstractas, dificilmente são usadas para comparação de ordens de crescimento entre duas específicas. O método conveniente de o fazer é baseado no calculo de limite da razão de duas funções: Ordem de crescimento usando limites 0 ordem de crescimento de t(n) < ordem de crescimento de g(n) c > 0 ordem de crescimento t(n) = ordem de crescimento de g(n) ∞ ordem de crescimento de t(n) > ordem de crescimento de g(n) Os dois primeiro casos significa que t(n)O(g(n)) e os dois últimos significa t(n)(g(n)) e o segundo caso implica que t(n) (g(n)) Exemplos: ◦ 10n vs. n2 ◦ n(n+1)/2 vs. n2 )( )( lim ng nt Exemplo Compare a ordem de crescimento das seguintes funções (½)n(n–1) e n2. Solução: Como o limite é igual a um número positivo, então as duas funções tem a mesma ordem de crescimento, assim sendo, (½)n(n–1)(n2) Ordem de crescimento de algumas funções importantes Todas funções logaritmicas loga n pertencem a mesma classe Θ(log n) não importa a sua base a > 1 Todos polinómios do mesmo grau k pertencem a mesma classe: akn k + ak-1n k-1 + … + a0 ∈Θ(n k) Funções exponencial an tem diferentes ordem de crescimento para diferentes valores da base a. ordem log n < ordem nα (α>0) < ordem an < order n! < ordem nn Classes de eficiência assintótica básicas 1 constante log n logaritmica n linear n log n n-log-n n2 Quadrática n3 Cúbica 2n exponencial n! factorial Análise matemática para algoritmo não recursivos Procedimento a seguir para o análise matemático do algoritmo não recursivo de algoritmo. 1. Encontre a variável que indica o tamanho de entrada. 2. Identifique a operação básica do algoritmo (normalmente isto encontra-se dentro do ciclo) 3. Verifique se o número de vezes que é executado a operação básica do algoritmo depende do tamanho de entrada. Se alem disso, isto depende também de uma outra propriedade, as eficiências do pior caso, o caso médio e se necessário, melhor caso devem ser analisadas em separado. 4. Construa o somatório expressando o numero de vezes a operação básica do algoritmo é executado. 5. Usando as formulas e regras de manipulação de somatórios, encontre uma forma próxima para a conta ou encontre a sua ordem de crescimento. Exemplo 1: Elemento máximo Algoritmo MaxElemento(A[0.. n–1]) //Determina o valor de maior elemento num dado vector //Entrada: Um vector A[0.. n–1] de números reais //Saida: O valor de maior elemento de A maxval < - A[0] para i <– 1 para n–1 faça se A[i] > maxval maxval <- A[i] retorna maxval Medida do tamanho de entrada -? Operação Básica -? (operação realizada na maioria das vezes) Quantas vezes é a operação básica executado? Exemplo2: Problema de Unicidade Algoritmo Unicidade(A[0.. n–1]) //Determina se todos elementos de um dado vector são distintos //Entrada: Um vector A[0.. n–1] //Saida: Retorna “verdade” se todos elementos no vector A são //distintos e “falso” caso contrário para i < - 1 para n – 2 faça para j < - i+1 para n – 1 faça se A[i] = A[j] retorna falso retorna verdade Medida do tamanho de entrada -? Operação Básica -? (operação realizada na maioria das vezes) Quantas vezes é executada a operação básica? Nota: são o pior caso e o melhor caso o mesmo? Example 2 – Análise do pior caso Dois casos - ambos igualmente ruim 1. Os dois últimos elementos são os únicos que são iguais 2. Não existem dois elementos iguais Quantas comparações são feitas para cada um desses casos? )( 222 )1( 1...)3()2()1( )1(1)1()1(1)( 2 22 2 0 2 0 2 0 2 1 nO nnnnn nnn ininn n i n i n i n ij piorC Exemplo 3: Multiplicação matricial Algoritmo MultMatricial(A[0..n–1, 0..n–1], B[0..n–1, 0..n–1]) //Multiplica duas matrizes de ordem n usando a definição //Entrada: Duas matrizes A e B de ordem n //Saida: Matriz C=AB para i < – 0 até n – 1 faça para j < – 0 até n – 1 faça para k < – 0 até n – 1 faça C[i, j] < – C[i, j] + A[i, k] * B[k, j] return C Medida do tamanho de entrada -? Operação Básica -? (operação realizada na maioria das vezes) Quantas vezes é a operação básica executado? Nota: são o pior caso e o melhor caso o mesmo? Pior caso 1 0 332 1 0 1 0 1 0 1 0 1 0 )()( )( 1)( n i n i n j n i n j n k nOnnnC nnC nC Exemplo 4: Contagem de dígitos binários Algoritmo Binário(n) //Entrada: Um número positivo n //Saída: A quantidade de digitos binário de n na sua representação binária. cont < - 1 enquanto n >1 faça cont <- cont +1 n<- n/2 retorna cont Este algoritmo não pode ser investigado exactamente do mesmo modo dos exemplos anteriores são. Qual é a operação feita com mais frequência? Quantas vezes isso acontece (somatórios não se aplica aqui) ◦ n é dividido ao meio cada vez assim que deve acontecer cerca de log2n vezes Plano de Análise de Algoritmos recursivos Decidir sobre um parâmetro que indica o tamanho de uma entrada. Identificar a operação básica do algoritmo. Verificar se o número de vezes que a operação básica é executada podem variar em diferentes entradas do mesmo tamanho. (Se for, os casos o pior, médio e melhor deve ser investigado separadamente.) Estabeleça uma relação de recorrência com uma condição inicial apropriado que expressa o número de vezes que a operação básica é executada. Resolver a recorrência (ou, pelo menos, estabelecer a ordem de crescimento da sua solução) usando o método de substituições por retrocesso ou outro método. Exemplo 1: Avaliação recursiva de n! Definição: n ! = 1 ∗ 2 ∗ … ∗(n – 1) ∗ n para n ≥ 1 e 0! = 1 Definição Recursiva de n!: ◦ F(n) = F(n – 1) ∗ n para n ≥ 1 e ◦ F(0) = 1 Algoritmo Fact(n) //Calcula recursivamente n! //Entrada: Um não negativo inteiro n //Saida: O factorial de n Se n=0 retorna 1 Senão retorna Fact(n – 1) * n Tamanho de entrada:___________ Operação básica:_______________________ Relação de recurrência:______________________________Resolver a recurrência para M(n) M(n) = M(n – 1) + 1, M(0) = 0 //recurrence, condição inicial Substituição por retrocesso M(n) = M(n – 1) + 1 = [M(n – 2)+1]+1 = M(n – 2)+2 = [M(n – 3)+1]+2 = M(n – 3)+3 Veja um padrão? M(n) = M(n –1)+1 = … = M(n – i)+i = … M(n – n)+n = n Muito trabalho para a resposta óbvia – O(n) Exemplo 2: A Torre de Hanói “enigma” Recorrência para o número de movimentos: Exemplo 2: A Torre de Hanói “enigma” Examplo 2: A Torre de Hanói “enigma” http://en.wikipedia.org/wiki/Tower_of_Hanoi http://www.cut-the-knot.org/recurrence/hanoi.shtml Solução Recursiva (Move n>1 discos de A para C) ◦ Move recursivamente n –1 discos de A para B (C é Auxiliar) ◦ Então move o maior disco de A para C ◦ Move recursivamente n –1 discos de B para C (A é Auxiliar) Análise Recursiva de Algoritmo ◦ M(n) = M(n –1) + 1 + M(n –1) para n>1 , M(1) = 1 ◦ M(n) = 2M(n –1)+1, M(1) = 1 Resolver recorrência para o número de movimentos M(n) = 2M(n-1) + 1, M(1) = 1 Use Substituição para trás. M(n) = 2M(n-1)+1 =2[2M(n-2)+1]+1 = 22M(n-2)+2+1 =22[2M(n-3)+1]+2+1 = 23M(n-3)+22+2+1 Padrão M(n) = 2iM(n-i)+2i-1+2i-2+…+2+1 = 2iM(n-i)+2i-1 Condição inicial: n=1 ou i = n-1 = 2n-1 algoritmo exponencial: ainda melhor Exemplo 3: Contagem de nºde bits Algoritmo BinRec //Entrada: Um número inteiro positivo //Saída: Se n = 1 retorna 1 Senão retorna BinRec(n/2) + 1 Operação básica: adição Relação de recorrência: A(n) = A( n/2) + 1 para n> 1, A(1) = 0 Problema: n / 2 faz com que a substituição por retrocesso não funcione quando n não é uma potência de 2 Estimado: apenas para casos em que n é uma potência de 2 Recorrência ligeiramente Actualizada A(2k) = A(2k-1) + 1 para k>0, A(20) = 0 Usar a substituição por retrocesso A(2k) = A(2k-1) + 1 = [A(2k-2) + 1]+1 = A(2k-2) + 2 = [A(2k-3) + 1]+2 = A(2k-3) + 3 … = A(2k-i) + i … = A(2k-k) + k Assim, A(2k) = A(1) + k = k n=2k e então k = log2n A(n) = log2n = Θ(log n) Números de Fibonacci Consideremos a sequencia de números de Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … definidos pela recorrência: F(n) = F(n – 1) + F(n – 2) para n > 1 (1) E duas condições iniciais F(0) =0 e F(1) = 1. (2) Os números de Fibonacci foram apresentados pelo Leonardo Fibonacci em 1202 como solução para o problema concernente ao tamanho da população de coelhos. Fórmula explicita para n-ésimo número de Fibonacci Para resolução do problema de Fibonacci teremos que usar o teorema que descreve a solução para equação linear homogénea de segunda ordem com coeficientes constante. ax(n) + bx(n – 1) + cx(n – 2) = 0 (3) Onde os coeficientes a, b e c são reais (a 0). Seja dada a equação característica da recorrência (3) ar2 + br + c = 0 (4) Teorema 1 Sejam r1 e r2 duas raízes da equação características (4) da relação de recorrência (3). Assim temos os seguintes casos: Caso 1: Se r1 e r2 são reais arbitrários, a solução geral da recorrência (3) é dada pela formula: x(n) = r1 n + r2 n onde e são constantes arbitrários Caso 2: Se r1 e r2 são iguais entre si, a solução geral da recorrência (3) é dada pela fórmula: x(n) = rn + nrn onde r = r1 = r2 e e são constantes arbitrárias. Caso 3: Se r1,2 = u iv são complexos e distintos, a solução geral da equação (3) é dada pela fórmula: x(n) =n[cos n + sen n] Onde = u2 + v2 , = arctan v/u e e são constantes arbitrárias Apliquemos teorema 1 para resolver o problema de número de Fibonacci, para isso, temos que reescrever a equação (1) da seguinte maneira: F(n) – F(n – 1) – F(n – 2) = 0 (5) Sua equação característica da equação (5) é r2 – r – 1 = 0 com raízes Como a equação característica tem duas raízes reais, usamos a fórmula indicada no caso 1 (6) 2 51 2 )1(411 2,1 r nn nF 2 51 2 51 )( Para F(0) = 0, F(1) = 1, temos: Resolvendo o sistema obtemos: =1/5 e = –1/5. Assim, substituindo esses valores na equação (6), temos: Algoritmos para calculo de números Fibonacci 1. Algoritmo Recursivo Algoritmo F(n) … se n<=1 então retorna n senão retorna F(n–1) + F(n–2) … Análise de eficiência deste algoritmo (TPC) a) Para número de vezes é executada a operação básica b) Para a função. 2. Algoritmo não recursivo Algoritmo Fib(n) … F[0]=0; F[1]1 para i de 2 até n passo 1 faça F[i] F[i–1] + F[i–2] retorna F[n] … Análise de eficiência deste algoritmo (TPC)
Compartilhar