Análise Assintótica de Funções

Prévia do material em texto

<p>Lista 1 - Análise assintótica</p><p>Aluno:Emerson Ferreira Da Silva</p><p>Prove algebricamente e graficamente para quais valores de n e quais constantes:</p><p>15. n2 - 200n -300 não é O(n), 2n³ - 7n + 1 = Ω(n³) e 2n³ - 7n + 1 é</p><p>Θ(n3)?</p><p>1. n² - 200n - 300 não é O(n)</p><p>Para que uma função f(n) seja O(g(n)), deve existir uma constante c > 0 e um valor n₀</p><p>tal que 0 ≤ f(n) ≤ c*g(n) para todo n > n₀. No caso de n² - 200n - 300 e n, não existe tal</p><p>constante c porque para n suficientemente grande, n² - 200n - 300 sempre será</p><p>maior do que qualquer múltiplo constante de n. Portanto, n² - 200n - 300 não é O(n).</p><p>2. 2n³ - 7n + 1 = Ω(n³)</p><p>Para que uma função f(n) seja Ω(g(n)), deve existir uma constante c > 0 e um valor n₀</p><p>tal que 0 ≤ c*g(n) ≤ f(n) para todo n > n₀. No caso de 2n³ - 7n + 1 e n³, podemos tomar</p><p>c = 1 e n₀ = 1, pois para todo n > 1, temos 0 ≤ n³ ≤ 2n³ - 7n + 1. Portanto, 2n³ - 7n + 1 é</p><p>Ω(n³).</p><p>3. 2n³ - 7n + 1 é Θ(n³)</p><p>Uma função f(n) é Θ(g(n)) se e somente se f(n) é O(g(n)) e f(n) é Ω(g(n)). Já</p><p>provamos que 2n³ - 7n + 1 é Ω(n³). Além disso, podemos ver que 2n³ - 7n + 1 é O(n³)</p><p>porque para n suficientemente grande, 2n³ - 7n + 1 será menor do que qualquer</p><p>múltiplo constante de n³. Portanto, 2n³ - 7n + 1 é Θ(n³).</p><p>Lista 2 - Recorrência - Método da Árvore de Recursão</p><p>Exercício 13</p><p>T(n) = T(n/2) +T(n/2) + n log n</p><p>Temos que desenhar uma árvore de recursão:</p><p>T(n)</p><p>/ \</p><p>T(n/2) T(n/2)</p><p>/ \ / \</p><p>T(n/4) T(n/4) T(n/4) T(n/4)</p><p>... ... ... ...</p><p>Cada nível da árvore contribui com (n log n)</p><p>para o custo total. Como a árvore tem (log n)</p><p>níveis, o custo total é (n log 2n)</p><p>.</p><p>Sendo então a solução para a equação de recorrência</p><p>T(n)=2T(n/2)+nlogn</p><p>é</p><p>T(n)=Θ(nlog2n)</p>