
_START_ARTICLE_
算法分析
_START_PARAGRAPH_
在计算机科学中，算法分析（英语：Analysis of algorithm）是分析执行一个给定算法需要消耗的计算资源数量（例如计算时间，存储器使用等）的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（时间复杂度）或者存储器位置数量（空间复杂度）。算法分析是计算复杂度理论的重要组成部分。_NEWLINE_理论分析常常利用渐近分析估计一个算法的复杂度，并使用大O符号、大Ω符号和大Θ符号作为标记。举例，二分查找所需的执行步骤数量与查找列表的长度之对数成正比，记为，简称为“对数时间”。通常使用渐近分析的原因是，同一算法的不同具体实现的效率可能有差别。但是，对于任何给定的算法，所有符合其设计者意图的实现，它们之间的性能差异应当仅仅是一个系数。_NEWLINE_精确分析算法的效率有时也是可行的，但这样的分析通常需要一些与具体实现相关的假设，称为计算模型。计算模型可以用抽象机器来定义，比如图灵机。或者可以假设某些基本操作在单位时间内可完成。_NEWLINE_假设二分查找的目标列表总共有n 个元素。如果我们假设单次查找可以在一个时间单位内完成，那么至多只需要 单位的时间就可以得到结果。这样的分析在有些场合非常重要。_NEWLINE_算法分析在实际工作中是非常重要的，因为使用低效率的算法会显著降低系统性能。在对运行时间要求极高的场合，耗时太长的算法得到的结果可能是过期或者无用的。低效率算法也会大量消耗计算资源。
_START_SECTION_
增长的阶
_START_PARAGRAPH_
非正式地，如果一个关于 的函数，乘以一个系数以后，能够为某个算法在输入数据大小 足够大的情况下的运行时间提供一个上界，那么称此算法按该函数的阶增长。一个等价的描述是，当输入大小 大于某个 时，存在某个常数，使得算法的运行时间总小于。常用大O符号对此进行描述。比如，插入排序的运行时间随数据大小二次增长，那么插入排序具有 的时间复杂度。大O符号通常用于表示某个算法在最差情况下的运行时间，但也可以用来表述平均情况的运行时间。比如，快速排序的最坏运行时间是，但是平均运行时间则是。
_START_SECTION_
其他运算资源的增长率分析
_START_PARAGRAPH_
运用与分析时间相同的方法可以分析其他运算资源的消耗情况，比如存储器空间的消耗。例如，考虑以下一段管理一个文件的内存使用的伪代码：_NEWLINE_while (文件打开)_NEWLINE_    令 n = 文件大小_NEWLINE_    for n 每增长100kb_NEWLINE_        为该文件分配多一倍的内存空间_NEWLINE_在这个例子里，当文件大小n 增长的时候，内存消耗会以指数增长，或 。这个速度非常快，很容易使得资源消耗失去控制。