演算法的divide-and-conquer的問題..
2011-05-21 10:55 am
multiplying two n bit numbers u and v straightforwardly requires O(n^2)steps.By using the divide-and-conquer approach, we can split the number into two equal parts and compute the product by the following method:
uv = (a*2^(n/2) + b)*(c*2^(n/2) + d) = ac*2^(n/2) + (ad+bc) * 2^(n/2) + bd
If ad+bc is computed as (a+b)(c+d) - ac -bd ,what is the computing time?
回答 (1)
2011-05-21 9:07 pm
✔ 最佳答案
T(n)= T(n/2)+T(n/2)+T(n/2)= 3T(n/2)設P(n)=T(2^n), 則P(n)=3P(n-1)
P(n)=k*3^n,
TIn)=P(log_2(n))= k*3^r (r= log_2(n) )
3^r= n^[log_2(3)]= n^(log3/log2) 約 n^1.585
故T(n)=k*n^(log3/log2) = O[n^(log3/log2)]
2011-05-21 13:49:51 補充：
要先會解一階差分方程式
P(n)=aP(n-1)+ b* c^n
a≠c時, P(n)=k* a^n + bc/(c-a)* c^n
a=c時, P(n)= k* a^n + b*n* c^n
2011-05-21 13:50:54 補充：
與線性ODE相似,通解=齊次解+特殊解
收錄日期: 2021-05-04 00:58:58
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20110521000015KK00991