判断两多项式之积是否等于另一多项式 - k76853的专栏 - 博客频道 - CSDN.NET
问题描述：判断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。
由于算法并不能总获得问题的正确解，显然该随机算法为蒙特卡洛算法。
Read full article from 判断两多项式之积是否等于另一多项式 - k76853的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment