Assuma a existência de um algoritmo mult ( x, y ) que faça a multiplicação de números binários com n bits cada, cujos inteiros associados são x e y, e que este algoritmo possua complexidade de tempo n^a, para a=log 2 3. Queremos converter um inteiro decimal 10^n em sua representação binária (Considere n uma potência de 2). Dylan precisava realizar esta tarefa, mas ele estava com muita fome. Então ele escreveu uma parte do algoritmo naquele instante e deixou o restante do algoritmo, assim como sua análise, para fazer após sua refeição. Seu algoritmo ficou assim:
função pot2bin(n)
se n=1 então:
retorne 1010
senão:
z = ??? % depois termino
retorne mult(z,z)
(a) Ajude Dylan. Termine seu algoritmo. Bom, acho que fica assim: z= pot2bin(n/2)
Resposta:
z=pot2bin(n / 2).
(b) Como Dylan fez um excelente curso de ASA e já estava bem alimentado, ele fez corretamente a análise de complexidade deste seu algoritmo. Qual resultado ele obteve?
Resposta:
T(n)=T(n / 2)+n^log 2 3. Pelo Teorema Mestre, temos: O(n^log 2 3).

Passo 1

Temos um inteiro decimal 10^n que queremos converter em binário usando uma função recursiva pot2bin(n). Além disso, contamos com um subalgoritmo mu<(x,y) que multiplica números binários de n bits em tempo O(n^a), onde a=log2 3.

Passo 2

Observamos que
10^n = l(10^n/2r)^2,
ou seja, basta obter a representação binária de 10^n/2 e depois elevar ao quadrado usando mu<.

Passo 3

Assim, completamos o algoritmo da seguinte forma:
função pot2bin(n)
se n=1 então:
retorne 1010 // “1010” é a representação binária de 10
senão:
z = pot2bin(n/2)
retorne mult(z, z)

Passo 4

Para analisar a complexidade, note que se T(n) é o custo de pot2bin(n), temos
T(1)=O(1),
T(n)=T(n/2)+Ol(n^log2 3r)

Passo 5

Aplicando o Teorema Mestre com a=1, b=2 e f(n)=n^log2 3, vemos que n^logb a=n^0=1 e f(n) cresce polinomialmente maior. Logo
T(n)=Thetal(n^log2 3r)

Resposta

(a) z = pot2bin(n/2)
(b) A complexidade é O n^log2 3

Exercícios relacionados