《算法技术手册》一2.4.7 性能不明显的计算

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

2.4.7 性能不明显的计算

在很多情况下,仅仅通过算法的描述(如加法和乘法)就可以分辨出算法的性能是线性级还是平方级的。例如,平方级的主要特征是嵌入的循环结构。但是,这样的直接分析对某些算法却无法使用。例2-5给出了GCD算法,该算法是由欧几里德设计,用于计算两个整数的最大公约数。
例2-5:欧几里得GCD 算法
public static void gcd (int a[], int b[], int gcd[]) {
if (isZero (a)) { assign (gcd, a); return; }
if (isZero (b)) { assign (gcd, b); return; }
a = copy (a); // 确保a和b都没有被修改
b = copy (b);
while (!isZero (b)) {

// 最后一个参数表示结果符号,这里可以忽略它,
// 因为我们总是用大数减去小数
// 注意如果a > b,compareTo(a, b)的结果为正数

if (compareTo (a, b) > 0) {

subtract (a, b, gcd, new int[1]); 
assign (a, gcd);

} else{

subtract (b, a, gcd, new int[1]); 
  assign (b, gcd);
}

}
// a的值就是原先a和b的最大公约数
assign (gcd, a);
}
这个算法不断地比较a和b,然后用大数减去小数直至得到0为止。其中的辅助函数(isZero、assign、compareTo和subtract)都可以在代码库中找到。
虽然这个算法可以计算出两个数的最大公约数,但是对于给定的输入规模,要经过多少次迭代,这个答案并不明显。由于每一次循环之后,a或者b都不会变为负数,因此能够保证的是这个算法一定会结束,但是某些GCD的计算可能会需要较长的时间,例如,该算法计算gcd(1000, 1)时会执行999步!很明显,这个算法的性能对于输入数据的敏感程度比乘法和加法算法要大得多。对于相同规模的输入来说,GCD算法的时间是随着输入数据的变化而变化的。GCD算法在计算(10k-1, 1) 的最大公约数时性能最差,它需要处理n=10k-1次循环!由于加法和减法在数据规模为n时的时间复杂度均为O(n),因此GCD算法可以被归类为O(n2)。
例2-6中ModGCD算法的性能要比例2-5的GCD实现好得多,这个算法使用取模计算a除以b的余数。
例2-6:ModGCD 算法计算最大公约数
public static void modgcd (int a[], int b[], int gcd[]) {
if (isZero(a)) { assign (gcd, a); return; }
if (isZero(b)) { assign (gcd, b); return; }

// 将a、b调整到相同位数,然后在其副本上进行计算
a = copy(normalize(a, b.length));
b = copy(normalize(b, a.length));
// 确保a比b大,同时返回最大公约数
int rc = compareTo(a,b);
if (rc == 0) { assign (gcd, a); return; }
if(rc < 0){ 
int t[]=b;
b=a;
a=t; 

}
int quot[] = new int[a.length];
int remainder[] = new int[a.length];
while (!isZero(b)) {
int t[] = copy (b);
divide (a, b, quot, remainder);
assign (b, remainder);
assign (a, t);
}
// a 的值就是原始的(a,b)的最大公约数
assign (gcd, a);
}
ModGCD能够更快地得到解,因为它不会在while循环中不断地从大数中减去小数。这个差异并不仅仅体现在实现细节上,也反映了在如何使用算法解决问题方面的一个根本性改变。
图2-5和表2-5展示了针对随机产生的142个n位数,求解所有10 011对整数对最大公约数的计算结果。
2017_09_20_100216
图2-5:比较gcd和modgcd算法
2017_09_20_100249
对于随机数据,即便ModGCD实现比对应的GCD实现约快3倍,它的性能依旧是平方级,也就是O(n2)。分析ModGCD算法的最坏情况有些难度,研究表明当ModGCD处理两个连续的Fibonacci数字时性能最差。从图2-5上也可以推断出算法是平方级的,因为算法性能在数据规模翻倍后变为原先的4倍。
计算最大公约数还有着更为优秀的算法,不过这些算法主要针对特别大的整数,因而在实际场景中并不实用。

相关文章
|
2天前
|
机器学习/深度学习 算法 数据可视化
基于BP神经网络的64QAM解调算法matlab性能仿真
**算法预览图省略** MATLAB 2022A版中,运用BP神经网络进行64QAM解调。64QAM通过6比特映射至64复数符号,提高数据速率。BP网络作为非线性解调器,学习失真信号到比特的映射,对抗信道噪声和多径效应。网络在处理非线性失真和复杂情况时展现高适应性和鲁棒性。核心代码部分未显示。
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
11天前
|
SQL 存储 算法
【MySQL技术内幕】6.4-锁的算法
【MySQL技术内幕】6.4-锁的算法
23 1
|
11天前
|
存储 算法 关系型数据库
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
【MySQL技术内幕】5.7- InnoDB存储引擎中的哈希算法
14 1
|
13天前
|
算法 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 语言的实现。
|
15天前
|
存储 自然语言处理 算法
编辑距离算法全解析:优化文本处理的关键技术
编辑距离算法全解析:优化文本处理的关键技术
|
14天前
|
算法
基于ADM自适应增量调制算法的matlab性能仿真
该文主要探讨基于MATLAB的ADM自适应增量调制算法仿真,对比ADM与DM算法。通过图表展示调制与解调效果,核心程序包括输入输出比较及SNR分析。ADM算法根据信号斜率动态调整量化步长,以适应信号变化。在MATLAB中实现ADM涉及定义输入信号、初始化参数、执行算法逻辑及性能评估。
|
17天前
|
算法
m基于PSO粒子群优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
MATLAB2022a仿真实现了基于遗传优化的NMS LDPC译码算法,优化归一化参数以提升纠错性能。NMS算法通过迭代处理低密度校验码,而PSO算法用于寻找最佳归一化因子。程序包含粒子群优化的迭代过程,根据误码率评估性能并更新解码参数。最终,展示了迭代次数与优化过程的关系,并绘制了SNR与误码率曲线。
20 2
|
18天前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
16 1

热门文章

最新文章