《算法技术手册》一2.4.6 二次方的算法性能

简介: 本节书摘来华章计算机《算法技术手册》一书中的第2章 ,第2.4.6节, George T.Heineman Gary Pollice Stanley Selkow 著 杨晨 曹如进 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.4.6 二次方的算法性能

现在考虑一个类似的问题:两个n位的整数相乘。例2-4展示了使用小学课堂上学过的算法实现的乘法运算,其中n位数字的表示方法与之前的加法一样。
例2-4:mult乘法的Java实现
public static void mult (int[] n1, int[] n2, int[] result) {
int pos = result.length-1;
// 清除所有的值
for (int i = 0; i < result.length; i++) { result[i] = 0; }
for (int m = n1.length-1; m>=0; m--) {
int off = n1.length-1 - m;
for (int n = n2.length-1; n>=0; n--,off++) {

  int prod = n1[m]*n2[n]; 
  // 计算部分和,并且加上进位
  result[pos-off] += prod % 10;
  result[pos-off-1] += result[pos-off]/10 + prod/10;
  result[pos-off] %= 10;
}

}
}
同样的,这里也会给出另外一种实现算法——times。这种算法避免了取模运算的高费用,并且忽略了当n1[m]等于0时不必要的内层计算(注意,这里并没有给出times算法实现,读者可以在提供的代码库中找到它)。times算法包含了203行生成的Java代码来消除两个取模操作。那么在需要额外的费用维护和管理生成代码时,这种衍生算法还能够减少总的性能费用吗?
表2-4给出了这些乘法算法的性能,乘法所使用的数据与加法使用的随机生成数据一致。图2-4采用图形化的方式来描述算法性能,可以看到,抛物曲线是平方级算法的典型标志。
2017_09_20_095648
2017_09_20_095722
图2-4:比较mult和times
如图2-4所示,虽然times衍生算法的速度是mult算法的1/2,但是times和mult展现了相同的渐近性能。mult2n / multn的比率大约是4,这证明了乘法的性能是平方级的。我们定义t(n)表示乘法算法在输入规模为n时的实际执行时间。根据这个定义,对于所有的n > n0来说,必然存在某些常数c(c > 0),满足t(n) ≤ c*n2。我们不需要知道c和n0的实际值是多少,只需要知道它们必然存在即可。这个mult算法实现在我们的平台上执行时,常数c为1/7,n0为16。
需要再次说明的是,修改算法实现来提升效率并不会改变算法是平方级性能的事实。尽管如此,还是有其他的算法(Zuras,1994)可以让n位数相乘的明显速度快于平方级。对于像数据加密这种需要频繁实现大数乘法的应用,这类算法非常重要。

相关文章
|
5天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
21 1
|
5天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
12 1
|
7天前
|
算法 C语言 Ruby
分形逃逸时间算法中的 Normalized Iteration Count(NIC)技术 让颜色更柔和
Normalized Iteration Count (NIC) 技术是一种提升逃逸时间算法中分形图像质量的方法,它产生更平滑的颜色过渡。数学公式表示为:`mu = n + 1 - log(log(|Z(n)|)) / log(p)`,其中 `Z(n)` 是迭代次数,`|Z(n)|` 是复数模长,`p` 通常取2。示例代码提供了 Ruby, Maxima 和 C 语言的实现。
|
8天前
|
算法
基于ADM自适应增量调制算法的matlab性能仿真
该文主要探讨基于MATLAB的ADM自适应增量调制算法仿真,对比ADM与DM算法。通过图表展示调制与解调效果,核心程序包括输入输出比较及SNR分析。ADM算法根据信号斜率动态调整量化步长,以适应信号变化。在MATLAB中实现ADM涉及定义输入信号、初始化参数、执行算法逻辑及性能评估。
|
9天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
12天前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
16 0
|
12天前
|
存储 运维 算法
社交软件红包技术解密(十三):微信团队首次揭秘微信红包算法,为何你抢到的是0.01元
本文中,我们将介绍几种主流的IM红包分配算法,相信聪明的你一定能从中窥见微信红包技术实现的一些奥秘。
13 0
|
14天前
|
算法 NoSQL Python
开山之作!Python数据与算法分析手册,登顶GitHub!
若把编写代码比作行军打仗,那么要想称霸沙场,不能仅靠手中的利刃,还需深谙兵法。 Python是一把利刃,数据结构与算法则是兵法。只有熟读兵法,才能使利刃所向披靡。只有洞彻数据结构与算法,才能真正精通Python。
|
15天前
|
存储 人工智能 算法
RAG技术的高级应用和算法
文章主要探讨了RAG技术的高级应用和算法,系统化地整理了各种方法。
|
15天前
|
机器学习/深度学习 数据采集 算法
基于机器学习的推荐算法构建技术详解
【6月更文挑战第4天】本文详述了构建基于机器学习的推荐算法,特别是协同过滤方法。从用户和物品相似性的角度,解释了用户-用户和物品-物品协同过滤的工作原理。涵盖了数据准备、预处理、特征工程、模型训练、评估优化及结果展示的构建流程。推荐算法在电商、视频和音乐平台广泛应用,未来将受益于大数据和AI技术的进步,提供更智能的推荐服务。

热门文章

最新文章