《程序员实用算法》试读:1.2修改算法

在计算机领域,一项正在进行的工作是,通过对算法进行改进以求获得最佳的性能。这种工作通常采用以下两种策略之一:优化现有的算法或者开发新的算法。这些策略具有截然不同的目标,应当加以区别看待。在优化算法的时候,一般不会尝试使其性能方程降级。例如,我们知道冒泡排序的平均性能是O(N2-N)。如果你必须使用冒泡排序,那么将希望确定在冒泡排序中执行的动作所耗费的时间非常短。也就是说,希望它的两个主要操作(比较列表中的元素并交换它们)执行得非常快。在应用程序的上下文中,需要付出相当大的努力来确保算法的实现是经过完全优化的。例如,需要确保在内存中而不是在磁盘上交换元素。通过处理每个数据项的处理所需的时间,可以节省大量的运行时间。通过对应用程序定制这种时间可有效地优化算法。不过,你还是无法避开以下事实:冒泡排序算法随着数据输入规模的增大,其性能开销也将呈几何级数增长。为了解决这个问题,就需要使用或设计一种新算法。

此时,开发人员的工作将经历从高度实用(优化)到抽象的过程。现在必须找到一种新方法,其性能比O(N2-N)更好。如果成功地使性能方程降级,就开发出了一种新算法。这种区别是重要的,因为它将以你的方法作为条件。在几乎所有的情况下,需要分析广泛的解决方案,选择其中之一,然后根据具体情况对其进行优化。在这个过程中,需要理解这个算法是如何工作的,以便确定优化工作最好的努力方向。

首先,应该应用标准技术:使输入/输出(I/O)减到最小,减少函数调用的次数,限制计算密集型操作,比如浮点运算和频繁使用除法运算。然后,必须确定执行得最频繁的算法元素。在冒泡排序中,比较和交换应该是需要强烈关注的主题。最后,要检查可能由于疏忽而导致特别缓慢的实现。最后这一点往往与查找最坏情况相似。你正在查找可能导致性能下降的任何不寻常的情况。通常,这些情况将出现在实现细节的深处,并且是一个通常合理但偶尔代价高昂的基本假定的结果。一个已知的示例是前面讨论过的快速排序算法。
原文地址:https://www.cnblogs.com/shihao/p/2146477.html