知识卡片
减法与取模改变公约数迭代
反复从较大非负整数减去较小值能保留最大公约数,但若一数为1,迭代次数随另一数值线性增长,相对于该数的位数可能是指数级。取模版一次用余数取代多次减法,迭代次数及每次大整数除法成本需要分别分析。
03158与03159的零值入口均写成:a为零时assign(gcd,a),b为零时assign(gcd,b);若assign的参数方向按同图后续assign(gcd,a)的注释理解为前者接收后者,则gcd(0,b>0)错误返回0而非b,gcd(a>0,0)也同样。辅助函数未展示,结论以该参数方向为前提;不能宣称已运行确认。
减法版对(1000,1)先把1000减至1需999次,再在相等分支把b减为0还需1次循环,源码总共1000轮,正文的999步只覆盖前半。03160–03161随机样本曲线不能单独证明最坏增长;代码和测试均未执行。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
MODGCD算法的性能要比例2-5的gcd实现好得多,这个算法使用取模计算一个数模b的余数。 例2-6:MODGCD算法计算最大公约数 MODGCD将能够更快地得到解,因为它不会不断地在while循环中从大数中减去小数。这个差异并不仅仅是实现细节的差异,它告诉我们,在解决问题时,要融会贯通。 图2-
参考来源
- 位置:《算法技术手册》第2章《讨论5b:性能不明显的计算》(spine1472;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1436.html;u037-ch02-014)。
- 结论依据:37全文、03158–03159完整代码、03160图和03161表实读,零值结论明确依赖未展示assign参数方向。
- 原始内容:MODGCD算法的性能要比例2-5的gcd实现好得多,这个算法使用取模计算一个数模b的余数。 例2-6:MODGCD算法计算最大公约数 MODGCD将能够更快地得到解,因为它不会不断地在while循环中从大数中减去小数。这个差异并不仅仅是实现细节的差异,它告诉我们,在解决问题时,要融会贯通。 图2-