3_Programação_2___Crescimento_de_funções

Prévia do material em texto

<p>Programação 2</p><p>Crescimento de funções</p><p>Thiago Amaral Guarnieri</p><p>Departamento Acadêmico de Ciência da Computação (DACC)</p><p>Universidade Federal de Rondônia - UNIR</p><p>24</p><p>1Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Vimos que a função de custo é dependente do valor de n:</p><p>▶ Número de comparações para para achar o maior elemento aumenta com n</p><p>▶ Parâmetro n fornece uma medida de dificuldade para resolver o problema</p><p>▶ Isto é, o tempo para resolver o problema cresce com n</p><p>24</p><p>2Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Para valores pequenos de n, qualquer algoritmo é rápido</p><p>▶ Mesmo os algoritmos ineficientes são rápidos</p><p>▶ Ou seja, a escolha do algoritmo não é um problema cŕıtico para para n</p><p>pequeno</p><p>▶ Em outras palavras, analisa-se o comportamento função de custo para</p><p>valores grandes de n, ou seja, seu comportamento assintótico</p><p>24</p><p>3Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Comportamento assintótico</p><p>O comportamento assintótico de f (n) representa o limite do comportamento do</p><p>custo quando n cresce.</p><p>▶ A análise de um algoritmo leva em conta apenas algumas operações</p><p>elementares. Dessa maneira, a função de custo está vinculada ao</p><p>crescimento assintótico delas</p><p>▶ No algoritmo de achar o maior número, o crescimento assintótico está</p><p>vinculado ao número de comparações</p><p>24</p><p>4Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Dentro do conceito de análise assintótica, temos a ideia de dominação, que</p><p>ajuda a entender o custo de um algoritmo a partir de uma entrada</p><p>suficientemente grande.</p><p>Dominação assintótica</p><p>Uma função f (n) domina assintoticamente outra função g(n) se existem duas</p><p>constantes positivas c e m tais que, para todo n ≥ m temos</p><p>|g(n)| ≤ c × |f (n)|</p><p>24</p><p>5Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Podemos observar a definição anterior por meio de um gráfico</p><p>▶ Depois de um m suficientemente grande, temos que a função g(n) sempre</p><p>vai ter um custo menor que uma função f (n)</p><p>▶ f (n) então serve como limite superior de complexidade para g(n)</p><p>24</p><p>6Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Exemplo 1: Sejam g(n) = n e f (n) = −n2.</p><p>▶ Temos que |n| ≤ c × | − n2| para todo n pertencente aos naturais. fazendo</p><p>c = 1 e considerando um m = 0, temos que a definição anterior é satisfeita.</p><p>Logo f (n) domina assintoticamente g(n).</p><p>▶ O contrário não é verdade porque | − n2| ≤ c × |n| apenas quando</p><p>n = {0, 1}</p><p>24</p><p>7Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Exemplo 2: Sejam g(n) = (n + 1)2 e f (n) = n2. Nesse caso temos uma</p><p>dominação assintótica bidirecional</p><p>▶ |(n + 1)2| ≤ c × |n2|. Para n = 0 isso não é verdade (|1| ≤ c × |0|)</p><p>▶ Vamos tentar para n = 1. A constante nesse caso é c ≥ (n2 + 2n + 1)/n2</p><p>▶ Substituindo n = 1, c ≥ 4.</p><p>▶ |n2| ≤ c × |(n+ 1)2|. Para n = 0 isso é verdade pois ficamos com 0 ≤ c × 1</p><p>para um c ≥ 0.</p><p>24</p><p>8Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>Knuth (1968) sugeriu uma notação para a dominação assintótica:</p><p>▶ se f (n) domina assintoticamente g(n), dizemos que g(n) = O(f (n))</p><p>▶ g(n) é da ordem de no máximo f (n)</p><p>▶ Observe que o sinal de igual (=) é um abuso de notação, uma vez que não</p><p>significa que uma coisa é igual a outra.</p><p>Exemplo: Quando dizemos que o tempo de execução T (n) é O(n2), isso</p><p>significa que existem constantes c e m tais que T (n) ≤ c × n2.</p><p>24</p><p>9Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Comportamento Assintótico de Funções</p><p>As funções de complexidade de tempo são definidas sobre inteiros não negativos.</p><p>A definição a seguir formaliza a notação de Knuth.</p><p>Notação O</p><p>Uma função g(n) é O(f (n)) se existem duas constantes positivas, c e m, tais que</p><p>g(n) ≤ cf (n), para todo n ≥ m</p><p>Exemplo 1: Sejam g(n) = (n + 1)2 e f (n) = n2. Já vimos que g(n) é O(n2),</p><p>quando c = 4 e n ≥ m = 1</p><p>24</p><p>10Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação O</p><p>Exemplo 2: Sejam g(n) = 3n3 + 2n2 + n e f (n) = n3. g(n) é O(n3).</p><p>▶ Isto é 3n3 + 2n2 + n ≤ c × n3</p><p>▶ Nossa constante tem que ser tal que c ≥ (3n3 + 2n2 + n)/n3.</p><p>▶ Substituindo n = 1 na equação temos c ≥ (3 + 2 + 1)/1 = 6</p><p>▶ Fazendo isso teremos g(n) = 3n3 + 2n2 + n ≤ 6n3</p><p>▶ g(n) também é O(n4). Porém essa afirmação é mais fraca.</p><p>Dica: sempre que os dois polinômios tiverem mesma ordem, sempre vai haver</p><p>uma constante c que permite demonstrar a dominação assintótica. Porque o que</p><p>domina o crescimento da função sempre é o elemento de maior ordem.</p><p>24</p><p>11Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação O</p><p>Exemplo 3: suponha que g(n) = n e f (n) = n2. Sabemos pela definição</p><p>anterior que g(n) = O(n2), pois para n ≥ 0 e c > 1, n ≤ cn2.</p><p>▶ No entanto f (n) não é O(n).</p><p>▶ Imagine que existam constantes c e m tais que para todo n ≥ m, n2 ≤ cn</p><p>▶ Na verdade estamos falando de n × n ≤ c × n, e não existe uma constante</p><p>c única que satisfaça a condição para qualquer n ≥ m</p><p>24</p><p>12Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação O</p><p>Exemplo 4: a função g(n) = log5 n é O(log n).</p><p>▶ Pela propriedade de mudança de base sabemos que logan = logxn</p><p>logxa</p><p>ou</p><p>logxa× logan = logxn</p><p>▶ Pela propriedade de simetria logxn = logxa× logan</p><p>▶ x = 5, c = logxa</p><p>24</p><p>13Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação O</p><p>Algumas operações podem ser realizadas com a notação O. As provas podem</p><p>ser encontradas em Knuth (1968) e Aho, Hopcroft e Ulman (1983)</p><p>24</p><p>14Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação O</p><p>Exemplo 1: A regra da soma O(f (n)) +O(g(n)) pode ser usada para calcular o</p><p>tempo de execução de uma sequência de trechos de programas</p><p>▶ Suponha três trechos com tempos de O(n), O(n2) e O(n log n)</p><p>▶ O tempo dos dois primeiros trechos é O(max(n, n2)), que é O(n2)</p><p>▶ Considerando o próximo trecho na sequência temos</p><p>O(max(n2, n log n)) que é O(n2)</p><p>24</p><p>15Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação O</p><p>Exemplo 2: [log n + k + O(1/n)]× [n + O(</p><p>√</p><p>n)]</p><p>▶ Prop. distributiva:</p><p>n log n + nk + nO(1/n) + log nO(</p><p>√</p><p>n) + kO(</p><p>√</p><p>n) + O(1/n)O(</p><p>√</p><p>n)</p><p>▶ Prop. 2:</p><p>n log n + nk + nO(1/n) + log nO(</p><p>√</p><p>n) + O(</p><p>√</p><p>n)+O(1/n)O(</p><p>√</p><p>n)</p><p>▶ Prop. 6:</p><p>n log n + nk + nO(1/n) + log nO(</p><p>√</p><p>n) + O(</p><p>√</p><p>n) + O(</p><p>√</p><p>n 1/n)</p><p>▶ Prop. 7:</p><p>n log n + nk + O(n1/n) + O(</p><p>√</p><p>n log n)+O(</p><p>√</p><p>n) + O(1/n</p><p>√</p><p>n)</p><p>▶ Prop. 5:</p><p>n log n + nk + O(max(n 1/n,</p><p>√</p><p>n log n,</p><p>√</p><p>n,</p><p>√</p><p>n 1/n))</p><p>n log n + nk + O(</p><p>√</p><p>n log n)</p><p>24</p><p>16Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação Ω</p><p>Notação Ω</p><p>Uma função g(n) é Ω(f (n)) se existirem duas constantes c e m tais que</p><p>g(n) ≥ cf (n) para todo n ≥ m</p><p>Ou seja, é uma notação complementar a notação O, pois determina o limite</p><p>inferior para o custo de uma função.</p><p>24</p><p>17Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação Ω</p><p>Exemplo 1: mostre que g(n) = 3n3 + 2n2 é Ω(n3)</p><p>▶ precisamos mostrar que 3n3 + 2n2 ≥ c(n3)</p><p>▶ Se escolhermos c = 1 e m = 0 já é o suficiente para garantir a desigualdade</p><p>24</p><p>18Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação Ω</p><p>Exemplo 2: Seja g(n) = n para n ≥ 1, ı́mpar, e g(n) = n2/10 para n ≥ 0, par.</p><p>▶ Vamos considerar o caso par porque tem maior custo</p><p>▶ Precisamos mostrar que n2/10 ≥ c(n2)</p><p>▶ Se escolhermos c = 1/10 já garantimos a desigualdade</p><p>24</p><p>19Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação Θ</p><p>Notação Θ</p><p>Uma função g(n) é Θ(f (n)) se existirem duas constantes positivas c1, c2 e m</p><p>tais que</p><p>0 ≤ c1f (n) ≤ g(n) ≤ c2f (n) para todo n ≥ m</p><p>Ou seja, é uma notação que determina um limite assintótico firme, pois g(n)</p><p>está entre a curva de c1f (n) e c2f (n)</p><p>24</p><p>20Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação Θ</p><p>Exemplo 1: seja g(n) = n2/3− 2n vamos mostrar que g(n) é Θ(n2).</p><p>Ou seja que c1n</p><p>2 ≤ n2/3− 2n ≤ c2n</p><p>2</p><p>▶ Dividindo por n2 obtemos c1 ≤ 1/3− 2/n ≤ c2</p><p>▶ O lado direito, 1/3− 2/n ≤ c2 é verdade para c2 = 1/3 e m > 0</p><p>▶ O lado esquerdo, c1 ≤ 1/3− 2/n ou c1 ≤ (n − 6)/3n</p><p>Para essa constante ser positiva n = 7 o que leva a c1 = 1/21</p><p>▶ logo c1 = 1/21, c2 = 1/3,m = 7</p><p>24</p><p>21Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação o</p><p>O limite assintótico superior O pode ser firme ou não</p><p>▶ Por exemplo, 2n2 é O(n2) é um limite assintoticamente firme</p><p>▶ No entanto, 2n é O(n2), mas este limite não é assintoticamente firme</p><p>A notação o é usada para quando o limite não é assintoticamente firme:</p><p>Notação o</p><p>Uma função g(n) é o(f (n)) se, para qualquer constante c > 0, então</p><p>0 ≤ g(n) ≤ cf (n) para todo n > m</p><p>Exemplo: 2n = o(n2) mas 2n2 ̸= o(n2), já que a desigualdade não vale para</p><p>c = 1.</p><p>24</p><p>22Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Notação ω</p><p>Por analogia, ω é o limite inferior não firme</p><p>Notação o</p><p>Uma função g(n) é ω(f (n)) se, para qualquer constante c > 0, então</p><p>0 ≤ cf (n) ≤ g(n) para todo n > m</p><p>Exemplo: n2/2 = ω(n) mas n2/2 ̸= ω(n2), já que a desigualdade não vale para</p><p>c = 1.</p><p>24</p><p>23Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Outras propriedades</p><p>As propriedades de números reais também valem para comparações assintóticas:</p><p>24</p><p>24Comportamento</p><p>Assintótico</p><p>Universidade Federal de</p><p>Rondônia - UNIR</p><p>Exerćıcios</p><p>Comportamento Assintótico</p>