题目内容
(请给出正确答案)
[主观题]
设是一个d次多项式.假设已有一算法能在O(i)时间内计算一个i次多项式与一个一次多项式的乘积,以
设是一个d次多项式.假设已有一算法能在O(i)时间内计算一个i次多项式与一个一次多项式的乘积,以及一个算法能在O(ilogi)时间内计算两个i次多项式的乘积.对于任意给定的d个整数,用分治法设计一个有效算法,计算出满足且最高次项系数为1的d次多项式P(x),并分析算法的效率.
查看答案
如果结果不匹配,请 联系老师 获取答案
设是一个d次多项式.假设已有一算法能在O(i)时间内计算一个i次多项式与一个一次多项式的乘积,以及一个算法能在O(ilogi)时间内计算两个i次多项式的乘积.对于任意给定的d个整数,用分治法设计一个有效算法,计算出满足且最高次项系数为1的d次多项式P(x),并分析算法的效率.
二叉搜索树中,然后对树进行中序遍历,并将元素按序放人数组a中,为简单起见,假设a中的数据互不相同。试编写一个函数,从一棵二叉搜索树中删除最大元素。要求函数的时间复杂性必须是O(h),其中h是二叉搜索树的高度。
写一算法检测单向链表中是否存在环
(whether there is a loop in a link list),
要求算法复杂度(Algorithm's complexity 是
O(n)) 并只使用常数空间(space is O(c)).
注意,你只知道一个指向单向链表头的指针。
链表的长度是不定的,而且环出现的地方也是不定
的,环有可能在头,有可能在中间。而且要求是检
测, 不能破坏环的结构.