请输入或粘贴题目内容
搜题
拍照、语音搜题，请扫码下载APP
题目内容
（请给出正确答案）
设
是一个d次多项式.假设已有一算法能在O(i)时间内计算一个i次多项式与一个一次多项式的乘积,以及一个算法能在O(ilogi)时间内计算两个i次多项式的乘积.对于任意给定的d个整数
,用分治法设计一个有效算法,计算出满足
且最高次项系数为1的d次多项式P(x),并分析算法的效率.
答案
更多“设是一个d次多项式.假设已有一算法能在O（i)时间内计算一个i次多项式与一个一次多项式的乘积,以”相关的问题
第1题
设n次多项式f(x)=s0xn+a1xn-1+…+an+an的根是a1，a2，…，an． 求
(i)以ca1，ca2，…，can为根的多项式，这里c是一个数；
(ii)以
第3题
第5题
设f(x)是一个多项式，用
表示把f(x)的系数分别换成它们的共轭数后所得多项式。证明：
(i)若g(x)|f(x)，那么
;
(i)若d(x)是f(x)和的一个最大公因式，并且d(x)的最高次项系数是1，那么d(x)的最高次项系数是1，那么d(x)是一个实系数多项式。
第7题
(1)试编写一个算法，求两个多项式的和。
(2)试编写一个算法，求两个多项式的乘积。
第8题
问题描述:设p是奇素数,1≤x≤p-1,如果存在一个整数y(1≤y≤p-1),使得x=y2(modp),则称y是x的模p平方根.例如,63是55的模103平方根.试设计一个求整数x的模p平方根的拉斯维加斯算法.算法的计算时间应为logp的多项式.
算法设计:设计一个拉斯维加斯算法,对于给定的奇素数p和整数x,计算x的模p平方根.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数p和x.
结果输出:将计算的x的模p平方根输出到文件output.txt.当不存在x的模p平方根时,输出0.
第9题
A.2
B.3
C.4
D.9
第10题
设单链表中结点的结构为：
在一个具有n个结点的单链表中插人一个新结点，并可以不保持原有顺序的算法的时间复杂度是().
A、O(1)
B、O(n)
C、O(n2)
D、O(nlog2n)
