算法及性能分析

算法设计是最具创造性的工作之一，人们解决任何问题的思想、方法和步骤实际上都可以认为是算法。人们解决问题的方法有好有坏，因此算法在性能上也就有高低之分。

算法

算法是指令的集合，是为了解决特定问题而规定的一系列操作。它是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据集合作为输出。算法通常来说具有一下五个特性：

输入：一个算法应以待解决的问题的信息作为输入

输出：输入对应指令集处理后得到的信息

可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成

有穷性：指令执行的指令个数是有限的，每个指令在有限时间内完成，因此整个算法也是在有限时间内可以结束的

确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的

简单的说，算法就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是算法的逻辑形式，后者是算法的代码形式

时间复杂性

在计算机资源中，最重要的就是时间与空间。评价一个算法性能的好坏，实际上就是评价算法的资源占用问题。

去掉表示算法运行时间中的低阶项和首项常数，就称我们是在度量算法的渐进时间复杂度，简称时间复杂度

空间复杂性

算法的空间复杂性同样是由算法运行时使用的空间来评价的。我们把算法使用的空间定义为：为了求解问题的实例而执行的操作所需要的存储空间的数目，但是它不包括用来存储输入实例的空间

算法时间复杂度分析

计算循环次数

分析最高频度的基本操作

最佳、最坏与平均情况分析

一般情况下，所有算法对于任何输入实例，它的时间复杂度都是相同的。但是有些算法的执行时间不但是规模的函数，也是输入实例数据元素初始顺序的实例

均摊分析

在均摊分析中，我们可以算出算法在整个执行过程中，或多次执行过程中所用时间的平均值，称为该算法的均摊运行时间。均摊分析保证了算法的平均代价，这与平均情况分析是不同的，在平均分析中必须知道每种输入实例的分布，计算所有不同输入实例才能得到平均值。

转载请注明：学时网 » 数据结构与算法基础（下）