Suponha você esteja escolhendo um dentre os três seguintes algoritmos para resolver um problema:
  • Algoritmo A resolve o problema dividindo-o em cinco subproblemas com metade do tamanho, resolve cada subproblema recursivamente e combina as soluções em tempo linear.
  • Algoritmo B resolve o problema de tamanho n recursivamente resolvendo dois subproblemas de tamanho n-1 e combina as soluções em tempo constante.
  • Algoritmo C resolve o problema dividindo-o em nove subproblemas com um terço do tamanho, resolve cada subproblema recursivamente e combina as soluções em tempo quadrático.
    (a) Quais são as fórmulas recursivas dos tempos desses algoritmos?
    Resposta:
    Algoritmo A: T(n)=5 T(n / 2)+O(n);
    Algoritmo B: T(n)=2 T(n-1)+O(1);
    Algoritmo C: T(n)=9 T(n / 3)+O(n^2).
    (b) Quais são as complexidades desses algoritmos?
    Resposta:
    Algoritmo A: Pelo Teorema Mestre, temos: a=5, b=2, f(n)=O(n) n^log b a= n^log 2 5>n^2, assim f(n)=O(n^log b a-varepsilon). Portanto, T(n)=O(n^log 2 5).
    Algoritmo B: Essa recorrência não se encaixa ao Teorema Mestre. Porén, observe que o número de subproblemas dobra n vezes combinando as soluções em tempo O(1). Dessa forma, T(n)=O(2^n).
    Algoritmo C: Pelo Teorema Mestre, temos: a=9, b=3, f(n)=O(n^2) n^log b a= n^log 3 9=n^2, assim f(n)=O(n^log b a). Portanto, T(n)=O(n^2 log n).
    © Qual desses algoritmos você escolheria caso quisesse o mais eficiente?
    Resposta:
    Algoritmo C.

Passo 1

O exercício apresenta três algoritmos recursivos (A, B e C) e pede para: 1) escrever as fórmulas recursivas de tempo, 2) determinar a complexidade assintótica de cada um, usando o Teorema Mestre ou outra técnica, e 3) escolher o mais eficiente. Vamos usar conceitos de recorrências e o Teorema Mestre quando possível.

Passo 2

As recorrências dos tempos de cada algoritmo são:
• Algoritmo A:
T(n)=5,Tl(tfrac n2r)+O(n)
• Algoritmo B:
T(n)=2,T(n-1)+O(1)
• Algoritmo C:
T(n)=9,Tl(tfrac n3r)+O(n^2)

Passo 3

Para o Algoritmo A aplicamos o Teorema Mestre com a=5, b=2 e f(n)=n. Temos
n^logb a=n^log2 5approx n^2,32
e f(n)=Ol(n^log2 5-varepsilonr) para varepsilonapprox1,32>0. É o caso 1 do Mestre, logo
T(n)=Thetal(n^log2 5r)

Passo 4

No Algoritmo B a recorrência não bate com o Mestre, mas note que cada redução de problema gera 2 subproblemas e diminui n em 1 até chegar a 1. Assim há n níveis de recursão, e o número total de chamadas é da ordem de 2^n. Como a combinação custa O(1),
T(n)=Theta(2^n)

Passo 5

Para o Algoritmo C aplicamos o Mestre com a=9, b=3 e f(n)=n^2. Aqui
n^logb a=n^log3 9=n^2
e f(n)=Thetal(n^logb ar), caso 2 do Mestre. Logo
T(n)=Thetal(n^2log nr)

Passo 6

Comparando as três complexidades: Theta(n^2,32), Theta(2^n) e Theta(n^2log n), o Algoritmo C ( n^2log n) é o mais eficiente para entradas grandes.

Resposta

Escolheria o Algoritmo C.

Exercícios relacionados