Análise de Algoritmo - Usp

03 – Análise de Algoritmos (parte 3) SCC201/501 - Introdução à Ciência de Computação II Prof. Moacir Ponti Jr. www.icmc.usp.br/~moacir Instituto de Ciências Matemáticas e de Computação – USP 2010/2 Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 1 / 38 Sumário 1 Análise Assintótica de Algoritmos Crescimento de funções Notação assintótica O Notação assintótica Notação assintótica Uso e relação entre as notações O, e Notações o e Regras 2 Funções 3 Dicas de análise na prática Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 2 / 38 Prévias: notícias e páginas interessantes a visitar Foi provado que qualquer posição do Cubo Mágico pode ser resolvida com 20 movimentos. http://www.reddit.com/tb/cz0ll Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 3 / 38 Crescimento de funções Análise assintótica de algoritmos geramente baseada em uma descrição em pseudo-código (ao invés de código fonte em determinada linguagem) caracteriza a complexidade de tempo como uma função do tamanho da entrada, n um algoritmo assintoticamente mais eficiente é a melhor escolha para todas as entradas, exceto as de tamanho pequeno. permite analisar a complexidade de um algoritmo independente do sistema computacional utilizado Moacir Ponti Jr. (ICMC–USP) 03–Análise de Algoritmos (p3) 2010/2 4 / 38 Sumário 1 Análise Assintótica de Algoritmos • Crescimento de funções • Notação assintótica O • Notação assintótica • Notação assintótica • Uso e relação entre as notações O, e • Notações o e • Regras 2 Funções 3 Dicas de análise na prática Moacir Ponti Jr. (ICMC–USP) 03–Análise de Algoritmos (p3) 2010/2 5 / 38 Notação assintótica: O (big oh) • Para uma dada função g n , denotamos O g n o conjunto de funções: O g n f n existem constantes positivas c e n0 tais que 0 f n c g n para todo n n0 • uma função f n pertence ao conjunto O g n se existe uma constante positiva c de forma que ela possa estar limitada por c g n para um valor de n suficientemente grande • podemos dizer que f n O g n , mas em geral se escreve f n O g n (abuso da notação de igualdade, não é simétrico) Moacir Ponti Jr. (ICMC–USP) 03–Análise de Algoritmos (p3) 2010/2 6 / 38 Notação assintótica: O (big oh) Para todos os valores de n à direita de n0, o valor de f n reside em c g n ou abaixo desse. Formalmente, a função g n é um limitante assintótico superior para f n Exemplo: 2n² O n³ - podemos pensar nessa equação como sendo 2n² O n³ ou 2n² O n³ - a taxa de crescimento de 2n² é menor ou igual à taxa de n³ Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 7 / 38 Notação assintótica: O (big oh) — exemplos Exemplo 1: 2n 10 é O n - podemos realizar uma manipulação para encontrar c e n0: 2n 10 c n c n 2n 10 c 2 n 10 n ≥ 10 / c - a afirmação é válida para c 3 e n0 10. Exemplo 2: n² é O n - é preciso encontrar c que seja sempre maior ou igual a n para todo valor de um n0: n² ≥ c n c é impossível pois c deve ser constante. Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 8 / 38 Notação assintótica: O (big oh) — exemplos Exemplo 3: 3n³ 20n² 5 é O n³ - é preciso encontrar c 0 e n0 1 tais que 3n³ 20n² 5 c n³ para n0 como 3n³ 20n² 5 20 n0 5³, podemos tomar c 28 e qualquer n0 1. Exemplo 4: 3log n 5 é O log n - é preciso encontrar c 0 e n0 1 tais que 3log 5 c log n para todo n0 note que 3log n 5 3 5 log n ≥ n 1 (log 1 0) assim, basta tomar, por exemplo, c 8 e qualquer n0 2 Exemplo 5: 2n² é O 2ⁿ - é preciso 0 e n0 1 tais que 2n² c 2ⁿ para todo n0 note que 2n² ≤ 2ⁿ para n ≥ 4 2ⁿ assim, basta tomar, por exemplo, c 4 e qualquer n0 4 Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 9 / 38 *Notação de igualdade para conjuntos de funções*: O • a igualdade nesse tipo de caso será utilizada no sentido de “representatividade” e pode ser lida como “é”. • um conjunto em uma fórmula representa uma função anônima naquele conjunto. • Exemplo 6: f n n³ O n² significa que existe um h n O n² de forma que f n n³ h n . • Exemplo 7: n² O O n² significa que, para qualquer f n O n existe h n O n² de forma que n² f n h n . Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 10 / 38 Sumário 1 Análise Assintótica de Algoritmos • Crescimento de funções • Notação assintótica O • Notação assintótica • Notação assintótica • Uso e relação entre as notações O, e • Notações e • Regras 2 Funções 3 Dicas de análise na prática Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 11 / 38 Notação assintótica: ∗ (omega) • Na maioria dos casos estamos interessados no limite superior, pois queremos saber no pior caso, qual a complexidade de tempo • Em alguns casos também podemos analisar o limite assintótico inferior para expressar algo que esteja “pelo menos” em um dado comportamento. • Para uma dada função g n , g n é o conjunto de funções: g n f n existem constantes positivas c e n0 tais que 0 c g n f n para todo n n0 • uma função f n pertence ao conjunto g n se existem uma constante positiva c tais que ela possa estar limitada por c g n para um valor de n suficientemente grande Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 12 / 38 Notação assintótica: (theta) • Para uma dada função g n , denotamos g n o conjunto de funções: g n f n existem constantes positivas c1, c2 e n0 tais que 0 c1g n f n c2g n para todo n n0 • uma função f n pertence ao conjunto g n se existem constantes positivas c1 e c2 tais que ela possa estar limitada entre c1g n e c2g n para um valor de n suficientemente grande Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 15 / 38 Notação assintótica: (omega) • Para todos os valores de n à direita de n0 , o valor de f n reside em c g n ou acima desse. • Exemplo: 3n2 n n - podemos pensar nessa equação como sendo 3n2 n n , - ou seja, a taxa de crescimento de 3n2 n é maior ou igual à taxa de n Fonte da figura: CORMEN et al. (2002) Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 13 / 38 *Notação de igualdade para conjuntos de funções*: • Exemplo 1: n lg n como n c lg n para c 0 podemos ler: “raiz de n é, pelo menos, omega de lg n “ para um n suficientemente grande (n n0 ). • Exemplo 2: 3n2 n n 3n2 n c n c 3n n c para n0 1 temos de pegar c 3 Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 14 / 38 Notação assintótica: (theta) também é possível mostrar que 6n^3 n^2 : suponha, a título de contradição, que existam c_2 e n_0 tais que: 6n^3 c_2 n^2 para n n_0. mas (após dividir por n^2 e manipular a desigualdade), n c_2 6 não é válido para n grande pois c_2 é constante Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 18 / 38 Notação assintótica: (theta) [Imagem de gráfico] Para todos os valores de n à direita de n_0, o valor de f n reside em c_1 g n ou acima dele e em c_2 g n ou abaixo desse. para todo n_0, f n g n dentro de um fator constante. Fonte da figura: CORMEN et al. (2002) Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 16 / 38 Notação assintótica: (theta) Foi dito que poderíamos descartar os termos de mais baixa ordem e coeficientes do termo de mais alta ordem. para mostrar formalmente que, por exemplo, 1/2 n^2 3n n^2 : definiremos constantes positivas c_1, c_2 e n_0 tais que: c_1 n^2 1/2 n^2 3n c_2 n^2 para todo n n_0. Dividindo por n^2: c_1 1 3/n c_2 a desigualdade do lado direito pode ser considerada válida para n 1 escolhendo c_2 1 2, e a do lado esquerdo pode ser considerada válida para n 7 escolhendo c_1 1 14. para c_2 1 2, n 7 e c_1 1 14, temos: 1/2 n^2 3n n^2 Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 17 / 38 Sumário 1 Análise Assintótica de Algoritmos • Crescimento de funções • Notação assintótica O • Notação assintótica • Notação assintótica • Uso e relação entre as notações O , e • Notações o e • Regras 2 Funções 3 Dicas de análise na prática Exemplo de uso da notação assintótica • Exemplo: para dois algoritmos quaisquer, considere as funções de eficiência: • f n 1000n • g n n² • f é maior do que g para valores pequenos de n • g cresce mais rapidamente, e finalmente resultará em maiores valores, sendo o ponto de mudança n 1000 • segundo as notações vistas, se existe um n₀ a partir do qual c f n é pelo menos tão grande quanto g n , então, desprezando os fatores constantes e considerando n₀ 1000 e c 1: o 1000n O n² ou f n O n² o que significa que para n 1000, n² é um limitante superior para 1000n. o mesmo aconteceria para n₀ 10 e c 100. Notação assintótica: relações e teorema Analogias O Teorema (1) para duas funções g n e f n , f n g n se e somente se: • f n O g n e • f n g n . Utilidade • utilizamos o teorema para demonstrar limites assintoticamente restritos a partir de limites assintóticos superiores e inferiores. Notações o e : notações “estritas” Muito parecidas com as notações O e , respectivamente. No entanto, a desigualdade deve valer para qualquer constante c: Para uma função g n , denotamos o g n o conjunto de funções: o g n f n para qualquer c 0 e n0 0 tais que 0 f n c g n para todo n n0 e g n o conjunto de funções: g n f n para qualquer c 0 e n0 0 tais que 0 c g n f n para todo n n0 f n g n se e somente se g n o f n e intuitivamente, (se o limite existe), para g n , lim f n 0 e para o g n lim f n 0 gn Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 22 / 38 Notações o e Exemplo 1: 2n^2 é o n^3 n^2 é sempre menor que n^3 para um n suficientemente grande, é preciso apenas determinar n0 em função de c 2n^2 c n^3 2n^2 c n^3 n^2 2 c n c 2 n 2 c 2 n0 n0 a desigualdade vale para n0 2 e c 2 Exemplo 2: 2n^3 não é o n^3 (ignorando as constantes) não podemos dizer que n^3 é sempre menor que n^3 para um n suficientemente grande. Exemplo 3: 1/2 n^2 é n^2 , mas 1/2 n^2 não é o n^2 , e 1/2 n^2 não é n^2 Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 23 / 38 Sumário 1 Análise Assintótica de Algoritmos Crescimento de funções Notação assintótica O Notação assintótica Notação assintótica Uso e relação entre as notações O, e Notações o e Regras 2 Funções 3 Dicas de análise na prática Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 24 / 38 Notação assintótica Algumas regras • Se T₁ n O f n e T₂ n O g n , então: T₁ n T₂ n max O f n O g n e T₁ n T₂ n O f n g n . • logₖ n O n para qualquer k pois logaritmos crescem muito lentamente Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 25 / 38 Notação assintótica ... Algumas regras • Se T x é um polinômio de grau n , então: T x xⁿ . Relembrando • um polinômio de grau n é uma função na forma: f x aₙ xⁿ aₙ₋₁ xⁿ⁻¹ a₀ x a₀ • classificação em função do grau 0: polinômio constante 1: função afim (ou polinômio linear, se a₀ 0) 2: polinômio quadrático 3: polinômio cúbico Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 26 / 38 Funções importantes (1/3) • Constante: 1 independente do tamanho de n, operações executadas um número fixo de vezes. • Logarítmica: log_b n típica de algoritmos que resolvem um problema transformando-o em problemas menores. para dobrar log_2 n é preciso fazer log_2 n². a base também muda pouco os valores: log_2 n 20 e log_10 n 6 para 1 000 000. • Linear: n em geral, uma certa quantidade de operações é realizada sobre cada um dos elementos de entrada. melhor situação para quando é preciso processar n elementos de entrada e obter n elementos de saída. Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 27 / 38 Funções importantes (2/3) Log linear (ou n log-n): n log_b n • típico de algoritmos que resolvem um problema transformando-o em problemas menores, resolvem cada um de forma independente e depois ajunta as soluções. • para dobrar n log n é preciso fazer aproximadamente n log_2 2n. Quadrática: n² • ocorre frequentemente quando os dados são processados aos pares, com laços de repetição aninhados. • sempre que n dobra, o tempo de execução é multiplicado por 4. • podem ser úteis para resolver problemas de tamanho relativamente pequeno. Cúbica: n³ • ocorre em multiplicações de matrizes, com três estruturas de repetição aninhadas. • sempre que n dobra, o tempo de execução é multiplicado por 8. • podem ser úteis para resolver problemas de tamanho relativamente pequeno (ou quando não se tem outra opção!). Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 28 / 38 Funções importantes (3/3) Exponencial: a^n • geralmente ocorre quando se usa uma solução de força bruta. • para o caso 2^n, sempre que n dobra, o tempo de execução é elevado ao quadrado. • não são úteis do ponto de vista prático. Fatorial: n! • é muitas vezes dito ter complexidade "exponencial", apesar de o fatorial ter comportamento muito pior. • geralmente ocorre quando se usa uma solução de força bruta. • para n 20, n 24 10¹⁸, • para o dobro n 40, n 8 2 10⁴⁷. • definitivamente, não são úteis do ponto de vista prático. Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 29 / 38 Funções e tempo cronológico Características Aproximadas do Hardware Número de Instruções executadas por Ciclo do relógio (IPC) 8 Frequência (1/ período do ciclo em min.) 3E+09 No. de Instruções por minuto 24E+09 T(n) n = 20 n = 40 n = 60 n = 80 1 5,3E-08 1,1E-07 1,6E-07 2,1E-07 n 2,3E-07 4,6E-07 6,9E-07 9,2E-07 n log n 1,6E-06 4,3E-06 6,0E-06 7,1E-05 n² 2,1E-05 4,6E-05 6,6E-05 1,7E-04 n³ 1,7E-04 4,8E-03 1,0E-02 1,5E-02 2^n 2,1 48,9 1,0 1,4E+03 n! 2,0E+03 5,4E+08 1,9E+18 6,6E+27 Fonte da figura: notas de aula do Prof. Ricardo Campello Moacir Ponti Jr. (ICMC-USP) 03–Análise de Algoritmos (p3) 2010/2 30 / 38 Exercício Um algoritmo tradicional e muito utilizado possui complexidade n¹⁵, enquanto um algoritmo novo proposto é da ordem de n log n: • f n n¹⁵ • g n n log n Qual algoritmo adotar? Uma possível solução: f n \frac{n¹⁵}{n} n^{0.5} n^0.5 2 n g n \frac{n \log n}{n} \log n^2 \log^2 n Como n cresce mais rapidamente do que qualquer potência de log, o algoritmo novo é mais eficiente. Moacir Ponti Jr. (ICMC–USP) 03–Análise de Algoritmos (p3) 2010/2 31 / 38 Dicas de análise na prática Se f n for um polinômio de grau d então f n é O n^d • despreze os termos de menor ordem • despreze os fatores constantes Use a menor classe de funções possível • 2n é O n , ao invés de 2n é O 2n Use a expressão mais simples • 3n 5 é O n , ao invés de 3n 5 é O 3n Moacir Ponti Jr. (ICMC–USP) 03–Análise de Algoritmos (p3) 2010/2 32 / 38 Dicas de análise na prática escala logarítmica Quadratic Quadratic Linear Linear Exemplo: n² vs. 10⁵n² e n vs. 10²n² 10⁵ Fonte da figura: notas de aula do Prof. Ricardo Campello Moacir Ponti Jr. (ICMC–USP) 03–Análise de Algoritmos (p3) 2010/2 33 / 38 Dicas de análise na prática Repetições: o tempo de execução é pelo menos o tempo dos comandos dentro da repetição multiplicada pelo número de vezes que é executada. o exemplo abaixo é O n para i de 1 ate n faca a = a*i Repetições aninhadas: análise feita de dentro para fora o tempo total é o tempo de execução dos comandos multiplicado pelo produto do tamanho de todas as repetições. o exemplo abaixo é O n^2 para i de 1 ate n faca para j de 0 ate n-1 faca a = a*(i+j) Dicas de análise na prática Há casos em que a análise assintótica ignora fatores assintoticamente irrelevantes, mas relevantes na prática: em especial quando temos interesse em entradas relativamente pequenas. Ao comparar dois algoritmos com tempo de execução: f n 10^100 n, e g n 10n log n pela análise assintótica, o primeiro é mais eficiente No entanto, 10^100 é o número estimado (por alguns astrônomos) como o limite superior para a quantidade de átomos no universo observável 10n log n 10^100 n apenas para n 2^1099