论文部分内容阅读
【摘 要】算法效率的高低直接决定一个算法的好坏，解决一个实际问题可以设计出很多的算法，但是其效率是不一样的，如在数组中查找一个元素，既可以一个元素一个元素的遍历，也可以对半查找，显然对半查找比遍历快得多，也就是说对半查找的效率要高。设计高效率的算法一直是计算机科学领域学者孜孜不倦的追求，本文将从实际问题入手，探究影响算法执行效率的因素，从而提出优化措施，总结优化经验，进而为日后设计高效率的算法奠定坚实的理论与实践基础。
【关键词】算法，效率，优化
算法效率通常使用算法的时间复杂度和空间复杂度来衡量，时间复杂度和空间复杂度又可以统称为时空复杂度。算法的时间复杂度关心算法关键部分代码的执行次数，如遍历一个长度为N的数组，那么关键代码需要执行N次，时间复杂度就为；算法的空间复杂度则主要关心算法运行时所需占用的存储空间。显然，一个好的算法其时间复杂度和空间复杂度都比较小。
一、影响算法效率的因素
影响算法效率的因素有很多，如问题的规模，显然问题规模越大算法执行时间越长；实现算法的编程语言也会影响算法效率，选择编译型语言要比解释型语言效率高，如选择使用C语言就要比选择使用Java语言实现算法效率高；数据结构的选择，设计合理的数据结构可以方便操作，减少空间占用；编译产生机器代码的质量，很多编译器会在产生机器代码时进行优化，从而提高算法效率；机器执行指令的速度，机器执行一条指令的速度越快那么算法的效率就越高。
上述影响算法效率的因素，有的可以通过更加巧妙的算法设计来规避冗余运算来提高效率，有的可以通过多核心并行来提高处理速度从而提高效率，接下来我们就探讨算法中提高效率的设计艺术。
二、提升算法效率的策略
（一） 递归转换为非递归实现
递归是一种常用的程序编写方式，它可以把一个大的复杂的问题转化为较小的相似的问题进行求解。然而，递归是通常过程或函数自己调用自己来实现的，它并不是一种高效的算法编写方式，在调用过程中系统需要处理断点，保存中断向量等，并且这些操作所以消耗的指令时间也远大于其他的指令开销。因此，实现算法时应当尽量将递归部分代码转换为非递归的方式实现。例如，计算N的阶乘，其递归算法可如下方式：
1 int F（int n）
2 {
3 if （n==1||n==0）
4 return 1；
5 else
6 return n* F（n-1）；
7 }
函数中的第六行代码调用函数自身，实现递归。使用非递归算法改写程序如下：
int F（int n）
{
if （n==0） reurn 1；
int x=1；
for（i=1；i<=n；i++）
x=x*i；
return x；
}
改写后的程序中取消了函数调用自身的代码，目的是为了减少因系统维护中断程序所需要花费的开销。此例只是一个简单的示例，通常，将递归算法改写为非递归算法时，需要用到栈来保存未完成的工作，需要时再将数据从栈中取出，在进行转换时，对递归函数的实现过程进行公式递推就可得出其非递归实现。
（二）设计合理的数据结构
合理的数据结构对算法的性能至关重要，一个合理的数据结构可以使用算法中对变量的访问更加便捷，同时也能减少变量所需的内存空间，从而提高算法的效率。例如，对于稀疏矩阵，如果矩阵中元素较多，那么就应该考虑压缩矩阵的存储空间，如果直接定义二维数组来存储矩阵，由于稀疏矩阵中存在大量零元素，那么势必会浪费大量的存储空间，此时可以考虑使用三元组（行号，列号，元素值）来存储稀疏矩阵，这样一来就能极大地压缩稀疏矩阵所占用的内存空间，同时遍历矩阵时也可以减少遍历次数，从而提高算法效率。此外，对于共享变量，通常可以使用联合体的方式，使多个变量共享同一段内存空间，这是通过降低算法的空间复杂度来提高算法效率的一种方法。
（三）通过并行计算降低算法执行时间
通过并行计算大幅降低算法执行时间有两种方式，一是在单机上多核心之间的并行；二是多机间的并行。目前，计算机硬件设备更新较快，主流计算机大多是双核心甚至是四核心，同时，计算机软件发展迅速，分布式系统日渐流行。然而，大多数的算法并没有针对多核心计算机或是分布式系统进行优化，依然是串行执行。通过对算法进行分析，将算法分为可并行部分和不可并行部分（即串行部分），将可并行部分分配给同一机器上不同的核心并行运行，或是将可并行部分分配给分布式系统中不同的主机运行，然后将结果汇总。在分布式系统进行并行计算时需要权衡算法的运算量和网络开销，从而作出一个合理的分配。
并行计算的方式并没有降低算法的时间复杂度，而是通过并行执行的方式减少了算法运行所需的时间，充分利用多核心计算机的硬件优势或是分布是系统的结构优势来提高算法的效率。
（四）借鉴已有的高效算法
目前已经存在大量公认的高效率的算法，我们在设计自己的算法时，可以充分借鉴这类算法来提高自己算法的效率。例如自己的算法中需要进行查找操作，这时就可以直接调用快速排序或堆排序算法，通过调用已有的高效率算法来改善自己算法的效率。
本文讨论了几种提高算法效率的方式，实际上设计算法是一项高难度的工作，对设计人员的理论基础和设计经验要求非常高，因此需要我们继续深入研究，不断推演新的优化策略。
参考文献：
[1]王成，赵金伟，闫桂荣. 基于综合统计法的算法效率分析和优化.[J].计算机工程.2010（22）
[2]童小明.超巨大规模的数值排序.[J].电脑编程技巧与维护.2012（19）
【关键词】算法，效率，优化
算法效率通常使用算法的时间复杂度和空间复杂度来衡量，时间复杂度和空间复杂度又可以统称为时空复杂度。算法的时间复杂度关心算法关键部分代码的执行次数，如遍历一个长度为N的数组，那么关键代码需要执行N次，时间复杂度就为；算法的空间复杂度则主要关心算法运行时所需占用的存储空间。显然，一个好的算法其时间复杂度和空间复杂度都比较小。
一、影响算法效率的因素
影响算法效率的因素有很多，如问题的规模，显然问题规模越大算法执行时间越长；实现算法的编程语言也会影响算法效率，选择编译型语言要比解释型语言效率高，如选择使用C语言就要比选择使用Java语言实现算法效率高；数据结构的选择，设计合理的数据结构可以方便操作，减少空间占用；编译产生机器代码的质量，很多编译器会在产生机器代码时进行优化，从而提高算法效率；机器执行指令的速度，机器执行一条指令的速度越快那么算法的效率就越高。
上述影响算法效率的因素，有的可以通过更加巧妙的算法设计来规避冗余运算来提高效率，有的可以通过多核心并行来提高处理速度从而提高效率，接下来我们就探讨算法中提高效率的设计艺术。
二、提升算法效率的策略
（一） 递归转换为非递归实现
递归是一种常用的程序编写方式，它可以把一个大的复杂的问题转化为较小的相似的问题进行求解。然而，递归是通常过程或函数自己调用自己来实现的，它并不是一种高效的算法编写方式，在调用过程中系统需要处理断点，保存中断向量等，并且这些操作所以消耗的指令时间也远大于其他的指令开销。因此，实现算法时应当尽量将递归部分代码转换为非递归的方式实现。例如，计算N的阶乘，其递归算法可如下方式：
1 int F（int n）
2 {
3 if （n==1||n==0）
4 return 1；
5 else
6 return n* F（n-1）；
7 }
函数中的第六行代码调用函数自身，实现递归。使用非递归算法改写程序如下：
int F（int n）
{
if （n==0） reurn 1；
int x=1；
for（i=1；i<=n；i++）
x=x*i；
return x；
}
改写后的程序中取消了函数调用自身的代码，目的是为了减少因系统维护中断程序所需要花费的开销。此例只是一个简单的示例，通常，将递归算法改写为非递归算法时，需要用到栈来保存未完成的工作，需要时再将数据从栈中取出，在进行转换时，对递归函数的实现过程进行公式递推就可得出其非递归实现。
（二）设计合理的数据结构
合理的数据结构对算法的性能至关重要，一个合理的数据结构可以使用算法中对变量的访问更加便捷，同时也能减少变量所需的内存空间，从而提高算法的效率。例如，对于稀疏矩阵，如果矩阵中元素较多，那么就应该考虑压缩矩阵的存储空间，如果直接定义二维数组来存储矩阵，由于稀疏矩阵中存在大量零元素，那么势必会浪费大量的存储空间，此时可以考虑使用三元组（行号，列号，元素值）来存储稀疏矩阵，这样一来就能极大地压缩稀疏矩阵所占用的内存空间，同时遍历矩阵时也可以减少遍历次数，从而提高算法效率。此外，对于共享变量，通常可以使用联合体的方式，使多个变量共享同一段内存空间，这是通过降低算法的空间复杂度来提高算法效率的一种方法。
（三）通过并行计算降低算法执行时间
通过并行计算大幅降低算法执行时间有两种方式，一是在单机上多核心之间的并行；二是多机间的并行。目前，计算机硬件设备更新较快，主流计算机大多是双核心甚至是四核心，同时，计算机软件发展迅速，分布式系统日渐流行。然而，大多数的算法并没有针对多核心计算机或是分布式系统进行优化，依然是串行执行。通过对算法进行分析，将算法分为可并行部分和不可并行部分（即串行部分），将可并行部分分配给同一机器上不同的核心并行运行，或是将可并行部分分配给分布式系统中不同的主机运行，然后将结果汇总。在分布式系统进行并行计算时需要权衡算法的运算量和网络开销，从而作出一个合理的分配。
并行计算的方式并没有降低算法的时间复杂度，而是通过并行执行的方式减少了算法运行所需的时间，充分利用多核心计算机的硬件优势或是分布是系统的结构优势来提高算法的效率。
（四）借鉴已有的高效算法
目前已经存在大量公认的高效率的算法，我们在设计自己的算法时，可以充分借鉴这类算法来提高自己算法的效率。例如自己的算法中需要进行查找操作，这时就可以直接调用快速排序或堆排序算法，通过调用已有的高效率算法来改善自己算法的效率。
本文讨论了几种提高算法效率的方式，实际上设计算法是一项高难度的工作，对设计人员的理论基础和设计经验要求非常高，因此需要我们继续深入研究，不断推演新的优化策略。
参考文献：
[1]王成，赵金伟，闫桂荣. 基于综合统计法的算法效率分析和优化.[J].计算机工程.2010（22）
[2]童小明.超巨大规模的数值排序.[J].电脑编程技巧与维护.2012（19）