Relações de Recorrência

Relações de recorrência expressam o tempo de execução de um algoritmo recursivo em termos de seu tempo de execução em entradas menores; resolvê-las produz os limites assintóticos de forma fechada usados para analisar algoritmos de "dividir para conquistar" e outros algoritmos recursivos.

Definition

Uma relação de recorrência é uma equação que define o valor de uma função em uma entrada em termos de seus valores em entradas menores; na análise de algoritmos, ela expressa o custo de um algoritmo em uma entrada de tamanho n em termos de seu custo em subproblemas menores.

Scope

Este tópico abrange a formulação e solução de recorrências que surgem na análise de algoritmos: o método de substituição, o método da árvore de recursão e o teorema mestre para recorrências de "dividir para conquistar" da forma T(n) = aT(n/b) + f(n). Ele explica como cada algoritmo recursivo induz uma recorrência e como traduzir essa recorrência em um limite "big-Theta". Exclui a própria notação assintótica, que é tratada separadamente, e os métodos de função geradora combinatória da matemática discreta.

Core questions

• Como um algoritmo recursivo dá origem a uma recorrência para seu tempo de execução?
• Como o método de substituição é usado para provar e verificar uma solução hipotética?
• Como o método da árvore de recursão expõe o trabalho total em todos os níveis de recursão?
• Quando o teorema mestre se aplica e o que significam seus três casos?
• Como são tratadas as recorrências que não se enquadram na forma do teorema mestre?

Key concepts

• relação de recorrência
• método de substituição
• método da árvore de recursão
• teorema mestre
• recorrência de dividir para conquistar
• caso base e caso recursivo
• solução de forma fechada
• método Akra-Bazzi

Key theories

Teorema mestre

Para recorrências de "dividir para conquistar" T(n) = aT(n/b) + f(n), o teorema mestre fornece a solução assintótica comparando f(n) com n elevado à potência log base b de a, cobrindo os três casos em que as folhas, a raiz ou os níveis balanceados dominam.

Métodos da árvore de recursão e de substituição

O método da árvore de recursão soma o trabalho realizado em cada nível de recursão para sugerir um limite, que o método de substituição prova rigorosamente por indução; juntos, eles lidam com recorrências além do escopo do teorema mestre.

Clinical relevance

A resolução de recorrências é o caminho padrão para determinar o tempo de execução de algoritmos recursivos, desde o "mergesort" e "quicksort" até a multiplicação rápida e muitos programas dinâmicos. Engenheiros e pesquisadores usam o teorema mestre rotineiramente para derivar e justificar as afirmações de complexidade assintótica associadas a tais algoritmos.

History

A análise de recorrência de algoritmos foi sistematizada em "The Art of Computer Programming" de Knuth. O teorema mestre tornou-se um pilar dos livros didáticos através do CLRS, e o método de Akra-Bazzi (1998) o generalizou para uma classe mais ampla de recorrências de "dividir para conquistar" com divisões desiguais.

Key figures

• Donald Knuth
• Mohamad Akra
• Louay Bazzi

Seminal works

• cormen2009
• knuth1997vol1

Frequently asked questions

Quando posso usar o teorema mestre?

O teorema mestre se aplica a recorrências da forma T(n) = aT(n/b) + f(n) com a >= 1 e b > 1, onde cada nível divide o problema em 'a' subproblemas de tamanho n/b. Recorrências com divisões desiguais, tamanhos de subproblemas variáveis ou custos de combinação não polinomiais podem exigir os métodos da árvore de recursão, substituição ou Akra-Bazzi.

Por que a recorrência do "mergesort" resulta em O(n log n)?

O "mergesort" resulta em T(n) = 2T(n/2) + O(n): dois subproblemas de metade do tamanho mais a fusão linear. Aqui, o trabalho por nível é o mesmo em todos os log n níveis da árvore de recursão, então o total é n vezes log n, o que o teorema mestre confirma como Theta(n log n).