Assuma a existência de um algoritmo mult (
) que faça a multiplicação de números binários com
bits cada, cujos inteiros associados são
e
, e que este algoritmo possua complexidade de tempo
, para
. Queremos converter um inteiro decimal
em sua representação binária (Considere
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:
pot2bin(n/2)
Resposta:
.
(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:
. Pelo Teorema Mestre, temos:
.
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:
Resposta:
(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:
Passo 1
Temos um inteiro decimal
que queremos converter em binário usando uma função recursiva
. Além disso, contamos com um subalgoritmo
que multiplica números binários de
bits em tempo
, onde
.
Passo 2
Observamos que
ou seja, basta obter a representação binária de
e depois elevar ao quadrado usando
.
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)
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
é o custo de
, temos
Passo 5
Aplicando o Teorema Mestre com
,
e
, vemos que
e
cresce polinomialmente maior. Logo
Resposta
(a) z = pot2bin(n/2)
(b) A complexidade é O
(b) A complexidade é O