Recorrências e Teorema Mestre

Introdução Teórica

A análise de complexidade de algoritmos recursivos frequentemente recai na resolução de relações de recorrência. Uma recorrência é uma equação que descreve uma função em termos de seus valores em entradas menores.

Métodos de Resolução

  1. Método da Substituição: Consiste em “chutar” um limite para a complexidade (ex: \(O(n \log n)\)) e provar por indução matemática que a hipótese é verdadeira.
  2. Árvore de Recursão: Visualizamos o custo de cada nível da recursão e somamos todos os níveis. É útil para gerar o “chute” para o método da substituição.
  3. Teorema Mestre: Uma ferramenta poderosa para recorrências da forma \(T(n) = aT(n/b) + f(n)\), onde \(a \ge 1\) subproblemas de tamanho \(n/b\) são gerados, e \(f(n)\) é o custo de dividir e combinar.

Os Três Casos do Teorema Mestre

Comparamos \(f(n)\) com \(n^{\log_b a}\) (o custo das folhas da árvore): * Caso 1: Se o peso está nas folhas (custo de divisão/combinação é “leve”), então \(T(n) = \Theta(n^{\log_b a})\). * Caso 2: Se o peso é distribuído igualmente (custo \(f(n)\) é comparável às folhas), então multiplicamos pela altura da árvore: \(T(n) = \Theta(n^{\log_b a} \log n)\). * Caso 3: Se o peso está na raiz (custo \(f(n)\) domina e satisfaz a condição de regularidade), então o custo total é proporcional a \(f(n)\), ou seja, \(T(n) = \Theta(f(n))\).

Problema Clássico

Problema: Onde está o Mármore? (Busca Binária) Link: Beecrowd 1025

Descrição: Dado um conjunto de mármores com números, e uma série de consultas, determinar se um número está presente e sua primeira posição após ordenação.

Solução: A Busca Binária é o exemplo clássico de recorrência \(T(n) = T(n/2) + O(1)\). * Aqui \(a=1, b=2, f(n)=1\). * \(n^{\log_2 1} = n^0 = 1\). * Caimos no Caso 2 do Teorema Mestre (\(1\) vs \(1\)), logo a complexidade é \(O(1 \cdot \log n) = O(\log n)\).

Para resolver o problema 1025: 1. Ordenar os mármores (Recorrência do MergeSort: \(2T(n/2) + n \to O(n \log n)\)). 2. Para cada consulta, usar busca binária (ou std::lower_bound em C++) para encontrar a primeira ocorrência.

Variações e Exercícios

  1. [Fibonacci, Quantas Chamadas?]
    • Foco: Entender como a falta de memoização gera uma árvore de recursão exponencial.
    • Link: Beecrowd 1029
  2. [Função de Ackermann]
    • Foco: Uma função recursiva que cresce extremamente rápido, ilustrando limites computacionais e complexidade não-polinomial.
    • Link: Beecrowd 1161 (Soma de Fatoriais - relacionado ao crescimento rápido)
Back to top