- Suponha que, para entradas de tamanho
, você tenha de escolher um entre dois algoritmos.
a) O algoritmo A resolve problemas dividindo-os em dois subproblemas de tamanho n-1, recursivamente resolve cada subproblema e então combina as soluções em tempo
.
b) Algoritmo B resolve problemas dividindo-os em nove subproblemas de tamanho n/3, recursivamente resolve cada subproblema e então combina as soluções em tempo
.
Qual o consumo de tempo desses algoritmos? Qual algoritmo é assintoticamente mais eficiente?
a) O algoritmo A resolve problemas dividindo-os em dois subproblemas de tamanho n-1, recursivamente resolve cada subproblema e então combina as soluções em tempo
b) Algoritmo B resolve problemas dividindo-os em nove subproblemas de tamanho n/3, recursivamente resolve cada subproblema e então combina as soluções em tempo
Qual o consumo de tempo desses algoritmos? Qual algoritmo é assintoticamente mais eficiente?
Passo 1
O enunciado pede para determinar a complexidade de dois algoritmos recursivos em função de
e depois compará-los assintoticamente. O conteúdo principal é resolver recorrências: para o algoritmo A usaremos expansão direta e, para o algoritmo B, o Teorema Mestre.
Passo 2
O algoritmo A satisfaz a recorrência
Para resolver, seja
uma constante tal que o tempo de combinação seja
. Então
Expansão por iterações:
e, após
passos,
Escolhendo
e supondo
, obtemos
Passo 3
O algoritmo B satisfaz a recorrência
Aplicando o Teorema Mestre:
-
, , -
, -
.
Como, estamos no caso 2 do Teorema Mestre e então
Passo 4
Comparando
versus
, fica claro que, para
grande,
cresce muito mais rápido que qualquer polinomial vezes logaritmo. Portanto o algoritmo B é assintoticamente mais eficiente que o algoritmo A.
Resposta
O algoritmo B é assintoticamente mais eficiente.