通常用来评判算法性能的三种情况是：最佳情况、平均情况与最坏情况。

ㅤ 对于任何算法来说，理解每种情况是如何产生的对于分析算法来说非常重要，因为算法在不同的情况下性能差异可能很大。 例如一种线性搜索的简单算法。线性搜索是一种自然的但效率低下的搜索技术，它简单地从数据集的头部顺序遍历到尾部。 在最佳情况下，要查找的元素处于数据集的第一个位置，所以在仅仅遍历一个元素之后就找到想查找的元素。 在最坏情况下，要查找的元素处于数据集的最后一个位置，所以必须在遍历完所有元素之后才能找到要查找的元素。 在平均情况下，可能会在数据集的中间某个位置找到元素。 许多算法在最坏情况下执行会消耗相当长的时间。 例如：在搜索元素时，数据集中根本就没有我们想查找的那个元素。 我们可以想象一下，这种情况在数据库的查找应用中经常出现。

考虑最坏情况分析的原因 考虑算法在最佳情况下的性能没有太多的意义，因为很多算法在最佳情况下的表现都相同。例如：在最佳情况下，几乎所有搜索算法都可以在一次查询中找到元素，而这并不能说明到底哪种算法更好，所以分析算法的最佳情况没有太多的意义。

分析算法平均情况下的性能往往不是那么容易。甚至我们很难去界定哪种情况叫做“平均情况”。通常我们不能精确地获得平均情况下的算法性能，这是因为我们无法准确地控制算法的执行状态。

最坏情况可以告诉我们算法性能的上限。分析一个算法的最坏情况可以保证在任何情况下此算法的表现都不会比最坏情况差，而其他情况肯定比最坏情况要好。

虽然我们把最坏情况当做很多算法性能的度量，但也有例外。因为有些时候我们也会用平均情况来评判算法性能。例如：随机算法中的快速排序算法，它使用了概率论的理论基础，从而有效地保证了平均情况下性能的准确性。

ㅤ O表示法是用来表示算法性能的最常见正式的标记法。 O表示法指明了一个函数的上限值。

常数项用O（1）表示。 当分析一个算法的运行时间时，如果知道无论它处理多大的数据量，它都至少得消耗一段固定的时间，那么就可以用常数项表示此固定的时间。 对某些常数c，正式地表述为：O（c）=O（1）

常量因子往往被忽略。 当分析一个算法的运行时间时，如果有某些任务都将执行相同数量的次数，就可以运用此规则。 例如：有三个任务的运行时间为T（n）=n，运行结果表示为O（3n），根据规则可以简化为O（n）。对某些常数c，正式地表述为：O（cT）=cO（T）=O（T）

加法运算取最大值。 当分析一个算法的运行时间时，如果一个任务在另一个任务之后顺序执行，可以运用此规则。 例如，有两个顺序执行的任务，其运行时间分别为：T（n）=n和T（n）=n²，运行结果表示为 O（n）+O（n²），根据规则，可以简化为O（n²）。 正式地表述为：O（T1）+O（T2）=O（T1+T2）=max（O（T1）, O（T2））

乘法结果不需要改变，但往往可以用更紧凑的方法表示。 当分析一个算法的运行时间时，如果一个任务的执行引起了另一个任务的迭代执行，可以运用此规则。例如：在一个嵌套循环中，外层迭代为T1，内层迭代为T2，如果T1（n）=n，T2（n）=n，那么运行结果表示为O（n）O（n）或O（n²）。 正式地表述为：O（T1）O（T2）=O（T1T2）

ㅤ

假设某算法的运行时间由函数T（n）=3n²+10n+10来表示。 若用O表示法，此函数可以简化为： O（T（n））=O（3n²+10n+10）=O（3n²）=O（n²） 这表明，当n增长到任意大时，算法的运行时间将主要由n²项来决定。随着n不断增大，我们可以通过每一项所占整个运行时间的百分比来证明这一点。 例如：当n=10时，计算结果如下： 3n²: 3×10²/（3×10²+10²+10）=73.2% 10n: 10²/（3×10²+10²+10）=24.4% 10: 10/（3×10²+10²+10）=24.4% 我们已经看到，n²占据了整个运行时间的大部分比例。 现在，考虑当n=100时的结果，如下： 3n²: 3×10²/（3×10²+10×100）+10）=96.7%（更大） 10n: 10×100）/（3×10²+10×100）+10） =3.2%（更小） 10: 10/（3×10²+10×100）+10） < 0.1%（更小） 这里我们可以看到，n²项占据了几乎整个运行时间，同时其他项的影响力变得更小。 ㅤ 下面按从快到慢的顺序列出了经常会遇到的5种大O运行时间 ❑ O(log n)，也叫对数时间，这样的算法包括二分查找。 ❑ O(n)，也叫线性时间，这样的算法包括简单查找。 ❑ O(n ＊ log n)，这样的算法包括快速排序——一种速度较快的排序算法。 ❑ O(n2)，这样的算法包括选择排序——一种速度较慢的排序算法。 ❑ O(n! )，这样的算法包括旅行商问题的解决方案——一种非常慢的算法。

ㅤ

在谈到算法的性能时，通常关注的是它的复杂度。 复杂度与它处理数据量所需要的资源（通常是时间）的增长速率密切相关。O表示法能够描述一个算法的复杂度。使用O表示法，通过观察算法的整体构造，我们很容易就可以描述最坏情况下的算法复杂度。有些时候，也会借助于利用迭代公式和统计方法。 为了理解复杂度，我们来看一种推测算法所用资源的方法。 假设有一种算法，它由k条语句组成，每条语句都要消耗ci资源（通常是时间）。 如果要计算它的整个运行时间，无论每条语句以什么顺序执行，我们只需要将它们的运行时间相加求和即可，也就是说从c1加到ck。通常每条语句并不是简单地按照顺序执行的，所以在计算整个运行时间时必须考虑其他更复杂的情况。

例如：有些语句是在循环中执行的，那么这样一些语句所 消耗的资源必须乘上迭代的次数。假设在这种算法中k=6，其中语句3-5均在循环中（1~n）执行，其他语句顺序执行，那么此算法的整体运行时间表示为：T（n）=c1+c2+n（c3+c4+c5）+c6。用O表示法的规则来计算，此算法的复杂度是O（n），因为可以忽略常数项。

用消耗固定资源的算法来分析问题是很透彻的。然而，当观察一个算法的整体构造时，只需要做两步：首先，必须知道算法的哪个部分是由非常量的数据决定的；然后，用函数列出每个部分的性能。那些消耗资源为常数项的部分在计算整个算法复杂度的过程中可以忽略。

在之前的例子中，假设T（n）表示算法的运行时间，我们必须明白，它的复杂度O（n）并没有具体表明运行此算法实际需要多少时间。换句话说，一个增长速率低的算法并不意味着它会消耗更少的运行时间。事实上，算法的复杂度并没有具体的计量单位。它只是表明当计算数据量的大小变化时，将如何影响算法所消耗的资源。 例如：用O（n）表示T（n）复杂度只说明算法的运行时间与因素n成正比，在特定n的取值条件下，T（n）能够达到上限值。正式地说，当我们谈到T（n）≤cn时，随着数据的变化，c作为一个常量因子不会影响到算法的运行时间。这就像在某种类型的计算机上运行算法，编译器会生成与算法有关的机器码和相关常量。

当n变化时，这些复杂度的增长速率是如何变化的 一些常见的复杂计算发生时的复杂度 图形式表示

就像一种算法的复杂度几乎不关注算法具体的运行时间，衡量算法的复杂度也没有高效或低效之说。虽然复杂度在一定程度上说明了算法的运算效率，但一个特定的复杂度要根据具体的情况来衡量它是否高效。 一般来说，在给定一定标准的情况下，能够使此算法表现最佳时，我们就认为此算法是高效的。通常，在解决同一个问题时，如果一种算法的复杂度比其他算法的复杂度都低，并且没有过多的常数项，我们就可以认为此算法是高效的。但也会有一些棘手的问题，在这些问题中，如果不设定一个近似值就无法找到一个“有效的”解决方法。这是一类特殊的问题，称为NP完全问题（NP-complete problem）。 虽然算法的复杂度是衡量算法性能的重要参考因素，但在实际应用中，通常还要考虑其他更多的因素。例如：当两种算法有同样的复杂度时，就得考虑对算法影响不太大的条件和因素。如果有种算法，数据量大小的变化对它的性能没有太大的影响，那么一个复杂度大且常量很小的算法所表现出的性能可能比一个复杂度小但常量很大的算法所表现出的性能更好。其他一些值得考虑的因素包括：算法的复杂度会如何维持和发展，以及如何使一种算法在实际中更加有效地实现。一个高效的实现并不能总是影响算法的复杂度，但它可以降低常量因素的影响，从而使算法在实际应用中更加高效。