|
大家都知道可以用计算机建立天气模型来预报天气，但是如果计算机需要花费几天时间才能预测出明天的天气，就成了无用的“马后炮”。因此我们要想办法来测量算法解题所需的时间。
解决办法不外乎以下两种：使用具备更快计算能力的超级计算机；或是找出更快的解题算法。
对于一个算法而言，它能正确解决给定的问题是最重要的，但是这个算法解决问题所需花费的时间也是至关重要的。之前讲过算法最终都必须终止，若某算法永远不终止或者在终止之前需要运行数十亿年，那么它不具备实际意义。
一般情况下，算法的运行时间随着问题的规模大小而变化：如果问题规模大十倍，那么运行时间会如何变化？之前我们举的find_max程序例子，它可以从一组正数中找出最大的数。那么对于包含1000个正数的列表和包含100个正数的列表，同样的算法运行的时间是否相同吗？或者前者需要的时间是后者的100倍？或者10倍？还是5倍？这种衡量某个算法运行时间与问题规模大小的关系，称为算法的时间复杂度。
为了测量算法的时间复杂度，一个简单的办法是我们可以在计算机上运行该算法，并对于不同规模大小的问题分别进行计时。例如，我们可以在长度范围为1到1000的列表上运行find_max（）并绘制时间变化结果图。这种方法比较直观，但是会有下面两个问题：
计算机执行不同操作的速度不同，例如加法运算非常快但是除法运算比较慢。而不同的电脑可能擅长不同的操作：一台机器可快速运行数学运算但对于字符串操作比较慢。另外，不同的计算机会有不同大小的内存以及不同性能的处理器、内存和硬盘。研究人员发现很难比较在不同机器上测量的结果。
其次，在某个给定范围内测量到的性能并不能告诉我们算法是否可以扩展到范围之外。对于1000个元素以内的列表输入，它可能运行得很好，但是在更大规模下，它可能会运行非常慢。
因此，若能确认算法需要的基本操作，那么通过计算算法运行所需的基本操作的数量，更能抽象地衡量算法的复杂度。例如，如果要测量计算正弦函数的算法的时间复杂度，可以假设只有加法，减法，乘法和除法才是基本运算。另一方面，如果要测量绘制圆的时间，则可以将正弦作为基本操作。
通常使用大写的字母O（Big-O表示法)来衡量算法的复杂性，它的形式是O加上一个函数O（<函数>），表示基本操作的数量与给定的O函数成正比。例如，如果算法需要2 *（n**2）次基本运算操作，那么它的复杂度写为O（n ** 2），而舍弃常数因子2。注意：n**2表示n的平方。
一些最常见的复杂性函数是： O（1）是恒定的时间复杂度。随着问题规模的增加，算法的操作次数实际上不会改变。 O（log n）是对数复杂度。这里对数的底没有区别，因为不同的底之间相差的只是常数因子（想想为什么？）。最常用的底是2。具有对数复杂度的算法可以很好处理大规模的问题。问题规模增加一倍，只需要增加固定数量的新操作，可能只需要一两个额外的步骤。 O（n）时间复杂度意味着算法是线性的;将问题规模扩大一倍也会使所需的操作数量翻倍。 O（n**2，n的2次方）是二次复杂度。将问题大小加倍可将操作计数乘以4。 10倍的问题需要多100倍的工作。O（n**3），O（n**4），O（n**5）等是多项式复杂度。 O（2**n，2的n次方）是指数复杂度。将问题大小增加1个单位可使工作量增加一倍。指数复杂度随问题规模变化非常快，导致这个算可能只能处理非常小规模的问题。
下图比较了各种时间复杂度的增长率。
（Big-O算法复杂度函数比较）
一般来说，如某个算法的复杂度是上述几项的合并，那么只需要保留增长最快的项。随着n的增加，增长较小的项对函数的增长没有太大贡献。例如，对于O（n**2+10n+5），如果n增加100倍，则n**2项将工作量增加10,000倍。而10n增加1000个操作基本可以忽略。因此对于该复杂度，可以删除10n+5，只保留O（n**2）。
除了算法的正确性，时间复杂度通常是算法最有趣的属性。但在某些情况下，算法所需的存储空间量也是令人感兴趣的。这些存储数量也使用Big-O表示法表示。例如，一个算法可能在不使用额外的内存情况下，具有O（n）时间；而另一个算法可能通过使用O（n）的额外存储而仅花费O（1）的时间。在这种情况下，需要根据将要运行它的环境来选择最佳算法。例如手机的内存可能比较少，那么可以选择第一种算法，以便尽可能少地使用内存，即使它速度较慢。而对于台式计算机，则可选择第二种算法使用更多的内存以获得更高的速度。
Big-O表示法是一个上限，一般表示在各种输入情形下，运行算法所需的最坏情况时间。但是，某些输入可能会使算法运行得更快。例如，搜索列表中的特定项目的算法，可能在它尝试的第一个项目上找到匹配。因此，在最佳情况下所需的工作量可能远低于最坏情况下所需的工作量。有一种表示法用于描述最佳情况下的复杂度，Big Omega 表示法。如果算法是Omega（<函数>），则最佳情况所需要的时间与该函数成比例。常见的快速排序算法是Omega（n * lg n）和O（n**2）。对于大多数输入（最佳情况），快速排序所需时间与n * lg n成比例，但对于某些输入（最坏情况），将需要与n**2成比例的时间。
此外，还有Big-Theta, Little-o,Little-omega等描述算法复杂度的函数。但是通常我们感兴趣的是最坏的情况，我们需要知道算法可能花费的最长时间，以便确定是否可以在合理的时间内解决问题，因此Big-O是描述算法复杂度的最常用函数。
|
