Método de substituição de recorrência §

---

O método de substituição é uma técnica utilizada para resolver recorrências, especialmente em algoritmos que têm uma estrutura de recursão. Ele envolve fazer uma suposição sobre a forma da solução e, em seguida, provar essa suposição por indução. Vamos explorar esse método em detalhes, passo a passo.

Estrutura do Método de Substituição §

1. Identificação da Recorrência: Primeiro, você deve ter uma recorrência a ser resolvida. Um exemplo típico é:

   onde:

   • é o tempo de execução para um problema de tamanho .
   • é o número de subproblemas.
   • é o tamanho de cada subproblema.
   • é o custo do trabalho fora das chamadas recursivas.

2. Suposição da Forma da Solução: Em seguida, você deve fazer uma suposição sobre a forma da solução. Por exemplo, suponha que para alguma constante . Essa suposição será testada.

3. Substituição na Recorrência: Substitua a suposição na recorrência original. Por exemplo, se você supõe que para alguma constante , você substitui isso na recorrência:

   Simplificando isso, você terá:

4. Verificação do Cálculo: Após a substituição, você precisa encontrar uma condição sobre e que faça a inequação verdadeira. Isso pode envolver escolher um valor apropriado para ou restringir .

5. Prova por Indução: A prova geralmente é feita usando indução matemática. Para provar a suposição, você mostra que é verdadeira para um caso base (por exemplo, ), e então você assume que é verdadeira para todos os casos até e prova para .

Exemplo Prático §

Vamos aplicar o método de substituição para resolver a seguinte recorrência:

Passo 1: Suposição §

Suponha que tem a forma . Vamos assumir que existe uma constante tal que:

Passo 2: Substituição §

Substituímos na recorrência:

Passo 3: Simplificação §

Agora, queremos mostrar que:

ou seja, queremos garantir que:

Isso é verdade se escolhermos suficientemente grande. Por exemplo, se escolhermos , a inequação se mantém para grande o suficiente.

Passo 4: Prova por Indução §

• Caso base: Para :

  está de acordo com .

• Passo Indutivo: Suponha que a suposição é verdadeira para e mostre que é verdadeira para .

Conclusão §

Após a verificação e a prova por indução, podemos concluir que:

O método de substituição é uma ferramenta poderosa e sistemática para resolver recorrências, especialmente em análises de algoritmos recursivos. Ele permite derivar limites assintóticos, ajudando a entender a eficiência dos algoritmos.

Referências §

---

Aula 2 - Análise de algoritmos