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 é:

   $$T(n)=a\cdot T\left(\frac{n}{b}\right)+f(n)$$

   onde:

   • $T(n)$ é o tempo de execução para um problema de tamanho $n$.
   • $a$ é o número de subproblemas.
   • $\frac{n}{b}$ é o tamanho de cada subproblema.
   • $f(n)$ é 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 $T(n)=O(n^k)$ para alguma constante $k$. 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 $T(n)\le c\cdot n^k$ para alguma constante $c$, você substitui isso na recorrência:

   $$T(n)\le a\cdot c{\left(\frac{n}{b}\right)}^k+f(n)$$

   Simplificando isso, você terá:

   $$T(n)\le \frac{a\cdot c}{b^k}{n}^k+f(n)$$

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

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, $T(1)$), e então você assume que é verdadeira para todos os casos até $n$ e prova para $n+1$.

Exemplo Prático

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

$$T(n)=2T\left(\frac{n}{2}\right)+n$$

Passo 1: Suposição

Suponha que $T(n)$ tem a forma $T(n)=O(n\log n)$. Vamos assumir que existe uma constante $c>0$ tal que:

$$T(n)\le cn\log n$$

Passo 2: Substituição

Substituímos na recorrência:

$$T(n)\le 2\cdot c\left(\frac{n}{2}\right)\log \left(\frac{n}{2}\right)+n$$ $$=2\cdot c\cdot \frac{n}{2}\left(\log n-1\right)+n$$ $$=cn\log n-cn+n$$

Passo 3: Simplificação

Agora, queremos mostrar que:

$$cn\log n-cn+n\le cn\log n$$

ou seja, queremos garantir que:

$$-n+n\le cn$$

Isso é verdade se escolhermos $c$ suficientemente grande. Por exemplo, se escolhermos $c\ge 1$, a inequação se mantém para $n$ grande o suficiente.

Passo 4: Prova por Indução

• Caso base: Para $n=1$:

  $$T(1)=O(1)$$

  está de acordo com $c\cdot 1\log 1=0$.

• Passo Indutivo: Suponha que a suposição é verdadeira para $n=k$ e mostre que é verdadeira para $n=k+1$.

Conclusão

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

$$T(n)=O(n\log n)$$

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