每周学点大数据 | No.4算法的分析之时间复杂度

No.4期

算法的分析之时间复杂度

小可：嗯，我觉得评价一个算法的最基本方式就是看它运行得快不快。

Mr. 王：嗯，这是重要的考量标准之一。研究算法运行得快不快的指标叫做时间复杂度。而在评价算法的同时还要考察其对内存空间的占用情况，也就是空间复杂度。这两个指标对于评价算法来说是最重要的。

小可：时间和空间都是计算机的资源，好的算法应该较少地占用资源而得出结果。

Mr. 王：对。我们先从时间复杂度开始探讨，空间复杂度与之类似，只不过是面向内存空间的。

小可：那时间复杂度是不是就是指一个算法运行的时间长短呢？

Mr. 王：不，这是一个常见的误解，算法的时间复杂度并不是指一个算法实际运行的时间。举个简单的例子，要访问一个集合中的每个数据，这在计算机科学中称为遍历。可以考虑一下，对一个只有10个数据的集合，和对有10000个同类型数据的集合使用同一种算法进行遍历，时间显然是不一样的。一个坏的算法在小的数据集合上，很可能比一个好的算法在大的数据集合上运行得要快。另外，现在计算机的发展速度很快，将同样的算法和同样的数据在不同的计算机上运行，得出结果的速度往往也不同。所以从这个角度来看，只用得出结果的时间这一指标来衡量，是不够准确和恰当的。

小可：对，算法的执行时间还跟数据量大小有关，也跟所使用的计算系统有关。

Mr. 王：的确，所以我们必须要考虑输入的数据规模。在算法分析中，这个数据规模常常用n来表示。对于不同的问题，n的单位也是不同的。在研究刚才的排序时，n代表的是有n个数；在研究数据库的查询时，n就表示有n条记录等。我们可以将关于数量级n的运行时间复杂度记为T(n)。

我们就用选择排序法来做个例子吧。这个算法可以分为两个部分：第一，我们要找出在未排序部分里的最小值并放在该放的位置上；第二，持续执行第一部分，直到所有的数据都已经排好序。假设进行比较需要消耗一个常数c的时间，中间更新假设最小值的时间和进行交换的时间忽略不计。那么进行一次扫描需要多久？

小可：那就是n和c的乘积cn。

Mr. 王：很好，但是每一次进行选择排序时，集合的大小都会缩小1，假设每次都发生了交换，你说说看整个算法的复杂性可以如何衡量？

小可：这样的扫描需要进行n−1次，因为只剩下一个数时就不用比了。而每次进行比较的元素次数分别是1, 2, 3,…, n−1。这是一个等差数列。结合前面的式子，可以求得为T(n)=(n−1+1)×(n−1)/2×c=cn(n−1)/2。

Mr. 王：于是，这个算法的复杂度为T(n)=O(n2)。

小可：这要怎么解释呢？

Mr. 王：假设n是一个很大的数，比如1010。那么常数c和n相比如何呢？

小可：常数c已经小到可以忽略不计了。

Mr. 王：同理，n和n2相比呢？

小可：那n也可以小到忽略不计了。

Mr. 王：在进行时间复杂度分析时，我们只保留多项式中的最高阶项。因为相比最高阶项而言，低阶项可以被忽略。同时，忽略其中的所有常数项系数。因为算法复杂度分析关注的是其数量级，而非具体的数值，当n是一个非常大的数时，n的幂值和c相比已经非常悬殊了，c的值小到对n的幂值不会产生太大的影响。另外，在计算复杂性理论中，有一个与这个问题相关的图灵机线性加速定理，这个定理证明了cna和na在复杂度分析上没有区别，感兴趣的话可以去查阅一下相关的资料。不管从哪个角度来看，都忽略在时间复杂度中所有的常数项系数。

回到我们的例子中，我们估计选择排序的运行时间是T(n)=cn(n−1)/2，转化成多项式的形式就是 。根据前面的约定，忽略多项式中的低阶项，只保留最高阶项，就是 ；还要忽略常数项系数，就是n2，所以T(n)的数量级就是O(n2)。

小可：那么前面的大O表示什么呢？

Mr. 王：嗯，这里需要说明一下。很多时候当n不够大时，时间多项式中的低阶部分确实没有高阶部分大。比如对于常数较大的n2+c，当n比较小的时候，c可能会比n2还大，这就不符合c和关于n高阶项相比小到可以忽略这个要求。而我们在研究算法的复杂性时，并不关心n比较小的时候算法的运行时间，因为这时一些处理时间为常数项或者低阶项的操作对算法运行时间的影响是非常大的，此时的运行时间不足以真正地代表一个算法的性能。所以引入了一系列记号对复杂度进行定义，要对n“较大”这个条件进行限制。

O(g(n))表示这样的一系列函数f(n)，存在正常数c和n0，对于所有的n大于n0，有0 f(n) c(g(n))。大O记号的含义是f(n)比g(n)低阶。换句话说，g(n)表示的是f(n)的上界。n0 的存在保障了我们研究的范围是n足够大时，它使得高阶项可以充分地大于低阶项。

小可：原来T(n)=O(g(n)) 就表示当n足够大时，T(n)要比g(n)小啊。

Mr. 王：通俗地讲是这样的。如果一个算法的运行时间T(n)=O(g(n))的话，则说明其运行时间的渐进上界是g(n)。也就是说，对于足够大的输入规模n，这个算法的运行时间不会超过g(n)。举个例子，选择排序的时间复杂度为O(n2)，如果输入规模是1010，那么它的运行时间应该在1020 这个数量级。

小可：这样看来，选择排序的运行时间应该会很久吧？

Mr. 王：是的，O(n2)这个数量级实际是比较大的，这说明选择排序并不是一个很好的排序算法。

另外还要注意一点，我们在实际做算法分析时，如果使用大O记号来表示一个算法的复杂度的话，所确定的g(n)一定要足够紧确，这样才能最好地代表一个算法的复杂性如何；因为我们去找一个很大很大的g(n)也能满足T(n)=O(g(n))，不过这样对于分析这个算法来说，就没什么意义了。

小可：比如一个算法的运行时间是T(n)=2n+3，那么它就是一个O(n)的算法，就定义而言，T(n)=O(n2)也是成立的。但是后者就不够紧确，这种不够紧确的时间界限不能真正地反映一个算法运行的时间界限。

Mr. 王：不错，这种O(n)的算法，也叫线性算法，说明它可以在与输入同规模的时间界限之内得出结论，与输入规模呈线性关系。如果一个算法的复杂度比线性算法还低，它就可以称为亚线性算法。比如O(logn)、O(loglogn)以及O(1)。O(1)也可以称作常数时间算法，我们注意到logn可以不写对数的底数，这同样也是对常数的一种忽略。这样忽略的原因其实非常简单，因为有对数换底公式，比如，在辅助度分析时，忽略前面的常数项系数，所以与同阶。在常用的写法中，我们会忽略对数的底数，在复杂度中表示的log与ln都是同阶的。另外，如果某个算法的时间复杂度T(n)可以表示为一个多项式，那么这个算法可以叫作多项式算法。对于一个不太大的数据规模，或者说在经典的计算理论中，我们认为这是一个易解问题；如果找不到多项式算法，比如找到的算法都是O(2n)级别的，我们会认为这是一个难解问题。

小可：嗯，当n比较大时，2的n次幂比关于n的多项式要大得太多了。如果一个O(2n)的算法真的有1010这样的输入规模，那可真是天文数字了。可是现实中真的有这样的算法吗？

Mr. 王：其实这种需要O(2n)的算法，还真的广泛存在。比如我要枚举一个集合的所有子集，你看看它的复杂度有多大。

小可：如果一个集合有n个元素，那么它的子集就有2n个！

Mr. 王：于是，子集的枚举就非常容易产生O(2n)这种高阶的复杂度。相比之下，比较高阶的复杂度还有O(n!)，指数函数和阶乘的增长速度都是非常快的，不难看出，在一个比较小的n值下，指数函数和阶乘都可以达到一个非常高的数量级。也就是说，一个拥有如此高阶复杂度的算法在同样的数据规模下运行时间往往是非常长的，一般来讲，这样的算法不是好的算法。就目前的知识看来，如果一个问题需要超过多项式时间界限的算法来解决，我们一般认为这个问题是一个难解问题。

内容来源：灯塔大数据