当前位置:牛骨文开发手册数据结构与算法小五的算法学习之路 》 判断两多项式之积是否等于另一多项式

问题描述:判断p(x),q(x)之积是否等于r(x),p,q,r分别为m,n,l 阶多项式

Random_polynomial(p(x),q(x),r(x),m,n,l)

输入:随机选取X[1:k]

输出:p(x)*q(x)是否等于r(x)

1          K =max{m+n,l}

2          For k=1 to K do

3              X[k] = random(real)    //no repeat

4          For k=1 to K do

5              If(p(X[k])* q(X[k])!= r(X[k])) then

6                  Return false

7          Return true

获得正确解的概率:

若p(x)q(x)与r(x)阶数相同成立,则对任意的k成立,输出正确解;若不成立,除非找到p(x)q(x)-r(x)=0的k个根,否则等式一定不成立。

设实数集合大小为S,则找到k个根的概率为max{m+n,l}/S,因此一定为错误解的概率为max{m+n,l}/S。

时间复杂度:O(max{m+n,l})

综上所述,若算法返回false则一定位正确解;若放回true,则正确解的概率为1-max{m+n,l}/S。

由于算法并不能总获得问题的正确解,显然该随机算法为蒙特卡洛算法。