知识卡片

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

同阶优化不排除更快算法

理解等级:中级

03155的mult对两组数字各遍历一次,每对位置计算部分乘积和进位;两个输入均为n位时核心循环执行n²次。表03157中规模加倍的时间比接近4支持该实验范围内的二次趋势,但有限数据和计时噪声不是对所有规模的严格证明。

作者另提alt跳过零位、减少取模,并报告约40%改善;图表呈现的是指定实现与样本,不保证所有数据均有这个比例。改变常数与改变渐近增长是不同结果,更快的大整数乘法可能采用不同算法,不能据当前双层循环推断乘法问题必有二次下界。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      二次方的算法性能 现在考虑一个类似的问题:两个n位的数相乘。例2-4是这个乘法的一个实现,采用小学使用的很简单的算法。 例2-4:Java的乘法实现mult 同样地,我们也会给出一个变形算法:alt,这个算法消除了取模运算的高开销,并且避开了当n1[m]等于0时不必要的内层计算(注意,alt算法没有

    参考来源

    - 位置:《算法技术手册》第2章《讨论5a:二次方的算法性能》(spine1471;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1435.html;u036-ch02-013)。 - 结论依据:36全文及03155源码、03156图、03157全部数据实读;alt源码未展示,不声称已读。 - 原始内容:二次方的算法性能 现在考虑一个类似的问题:两个n位的数相乘。例2-4是这个乘法的一个实现,采用小学使用的很简单的算法。 例2-4:Java的乘法实现mult 同样地,我们也会给出一个变形算法:alt,这个算法消除了取模运算的高开销,并且避开了当n1[m]等于0时不必要的内层计算(注意,alt算法没有