搜搜做题作业网一元多项式（加法、减法、乘法）时间和空间复杂度计算和比较
来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：数学作业 时间：2024/07/22 06:01:55
一元多项式（加法、减法、乘法）时间和空间复杂度计算和比较
两个多项式,一个为m阶,一个为n阶
两个多项式,一个为m阶,一个为n阶
假设都是链接存储
1、时间复杂度
加减法：O(m + n)
乘法：一般是O(mn)
2、空间复杂度：
加减法：两个多项式原地合并为O(1),需要开辟新空间则为O(m + n)
乘法：一般最坏是O(mn)
再问： 一般最坏是什么意思？
再答： 就是两个多项式乘法乘出来的所有项都没有次数重复的：(1 + x + x^2)(7x ^10 + 8x^20)，结果不就是有3 * 2 = 6项，没有一项是可以合并的
1、时间复杂度
加减法：O(m + n)
乘法：一般是O(mn)
2、空间复杂度：
加减法：两个多项式原地合并为O(1),需要开辟新空间则为O(m + n)
乘法：一般最坏是O(mn)
再问： 一般最坏是什么意思？
再答： 就是两个多项式乘法乘出来的所有项都没有次数重复的：(1 + x + x^2)(7x ^10 + 8x^20)，结果不就是有3 * 2 = 6项，没有一项是可以合并的