知识卡片

普通读书笔记卡 · 1708.b.3.m · 生成模型:未记录

减法与取模改变公约数迭代

理解等级:中级

反复从较大非负整数减去较小值能保留最大公约数,但若一数为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-