知识卡片
逐项重算乘积增加求值成本
本章先构造差商系数,O(n²);求每个目标值时,对第j项从头连乘j个(z−xi),全部项的乘法数为1+…+(n−1),所以每点O(n²)。总上界写O(n²+mn²),既包含预处理,也保留m=0时仍构系数的工作。
原文说额外因子m对复杂度影响不大不准确:目标数量增长会直接放大求值工作。若按牛顿嵌套形式或逐项复用累积乘积,可把每点算术工作降至O(n),但这是可推导的另一求值方式,不是当前源码已实现。
无论采用哪种运算次数模型,浮点误差和节点问题仍需另处理;减少乘法不能自动证明估值足够准确。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
term需要做1次乘法;当j为2时,term需要做2次乘法,持续这个过程直到j为n-1时,term需要做n-1次乘法。实际上,这就成了对1~n-1的整数求和,得到的计算时间为T(n)=(n(n+1)/2)-n,再乘以某段恒定的时间。(这是由计算等差数列的著名公式得到的。)在大O记法中,可化简为O(n
参考来源
- 位置:《算法精解:C语言描述》第13章《多项式插值的实现与分析》(spine1362;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1328.html;u232-ch13-009)。
- 结论依据:232全部成本推导和02992完整j/i嵌套循环实读;重用乘积为按已读牛顿基结构的读者推导,未改写/测试代码或虚称原实现更快。
- 原始内容:term需要做1次乘法;当j为2时,term需要做2次乘法,持续这个过程直到j为n-1时,term需要做n-1次乘法。实际上,这就成了对1~n-1的整数求和,得到的计算时间为T(n)=(n(n+1)/2)-n,再乘以某段恒定的时间。(这是由计算等差数列的著名公式得到的。)在大O记法中,可化简为O(n