Ex 2_25 n位十进制整数转换为二进制形式..._第四次作业

Ex 2_25 n位十进制整数转换为二进制形式..._第四次作业

Ex 2_25 n位十进制整数转换为二进制形式..._第四次作业

(a)   当n=1时,(10)d=(1010)b

当n=2时,(100)d=(10)d x (10)d=(1010)b x (1010)b

当n=4时,(10000)d=(100)d x (100)d=(1010)b x (1010)b x (1010)b x (1010)b

因此z=pwr2bin(n/2)

T(n)=T(n/2)+(cn/2)log23=>T(n)=O(nlog23)

(b)

若十进制整数x的位数等于1,则返回binary[x]

假设位数为n(n>1且n为2的幂),则把x平均分成两部分xL和xR,每一部分为n/2位

则x=10n/2*xL+xR=pwr2bin(n/2)*dec2bin(xL)+dec2bin(xR)

=fastMultiply(pwr2bin(n/2),dec2bin(xL))+dec2bin(xR)

运行时间为

T(n)=2T(n)+O(nlog23)=>T(n)=O(nlog23)

上一篇:安装python的mysqlclient==1.4.6报错


下一篇:未能正确加载“Microsoft.VisualStudio.Editor.Implementation.EditorPackage“提示信息