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
recursivamente resolvendo dois subproblemas de tamanho
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:
;
Algoritmo B:
;
Algoritmo C:
.
(b) Quais são as complexidades desses algoritmos?
Resposta:
Algoritmo A: Pelo Teorema Mestre, temos:
, assim
. Portanto,
.
Algoritmo B: Essa recorrência não se encaixa ao Teorema Mestre. Porén, observe que o número de subproblemas dobra
vezes combinando as soluções em tempo
. Dessa forma,
.
Algoritmo C: Pelo Teorema Mestre, temos:
, assim
. Portanto,
.
© Qual desses algoritmos você escolheria caso quisesse o mais eficiente?
Resposta:
Algoritmo C.
(a) Quais são as fórmulas recursivas dos tempos desses algoritmos?
Resposta:
Algoritmo A:
Algoritmo B:
Algoritmo C:
(b) Quais são as complexidades desses algoritmos?
Resposta:
Algoritmo A: Pelo Teorema Mestre, temos:
Algoritmo B: Essa recorrência não se encaixa ao Teorema Mestre. Porén, observe que o número de subproblemas dobra
Algoritmo C: Pelo Teorema Mestre, temos:
© 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:
• Algoritmo A:
• Algoritmo B:
• Algoritmo C:
Passo 3
Para o Algoritmo A aplicamos o Teorema Mestre com
,
e
. Temos
e
para
. É o caso 1 do Mestre, logo
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
em 1 até chegar a
. Assim há
níveis de recursão, e o número total de chamadas é da ordem de
. Como a combinação custa
,
Passo 5
Para o Algoritmo C aplicamos o Mestre com
,
e
. Aqui
e
, caso 2 do Mestre. Logo
Passo 6
Comparando as três complexidades:
,
e
, o Algoritmo C (
) é o mais eficiente para entradas grandes.
Resposta
Escolheria o Algoritmo C.