一篇温和的算法复杂度分析入门介绍(译文)

作者:Dionysis “dionyziz” Zindros <dionyziz@gmail.com>
译者:Kholin
原文:http://discrete.gr/complexity/

前言

如今有大量的程序员从业者,他们制造了一些最酷和最有用的软件,比如我们每天在互联网上看到的和日常使用的那些,这些程序员中的大多数并没有什么理论计算机科学的学习背景,但他们依然很棒并且很有创意,我们要感谢他们建造了这一切。

然而,理论计算机科学有其用途和应用,而且是相当实用的。这篇文章是写给那些熟悉自己的技能但是却没有任何理论性的计算机科学背景的程序员,我会介绍计算机科学中最实用的工具:大O符号和算法复杂度分析。作为一个同时供职于计算机学院和在工业领域中构建产品级软件的人,这是我在实践中发现的真正有用的工具之一,我希望读完这篇文章后,你能将其应用到你的代码中,让你的工作变得更加优秀。读完此文,你应该能够理解计算机科学家们经常使用的术语,比如“大O”、“渐进分析”以及“最坏情形分析”。

这些文字也写给来自希腊或全世界任何地方参与国际信息学奥林匹克竞赛、算法竞赛或其他类似竞赛的初中生和高中生们。正因如此,这篇文章没有任何数学的预备知识的要求,你将会学到相关的数学知识背景,从而能够继续学习算法,同时也能更加透彻的理解算法背后的理论。作为一个曾经参与这些学生竞赛的人,我强烈建议你通读这份引导资料,并且尝试完全理解,因为这些知识对于你学习算法和其他高级技术是必需的。

我认为这篇文章对于那些没有太多计算机理论学习经验的程序员是非常有帮助的(有些非常励志的软件工程师从来没有上过大学,这是事实)。但是由于这篇文章同时写给学生们看,所以有时会听起来像是一篇课文。另外,文中的某些主题可能对你来说再熟悉不过了,你应该在高中时期就已经见过了。如果这些部分你觉得已经理解了,那么可以跳过。其他部分会逐渐深入,并且有点偏理论化,如果你是参与竞赛的学生,那么你需要学习的理论性的算法可能比一般的从业人员多一些。当然,这些东西依然是很容易读懂的,不会难到让你望而却步,所以很可能值得你花时间去学习。由于原文是针对高中生的,不需要任何数学知识背景,因此任何有编程经验的人(也就是说你至少知道递归是什么意思)都能不带任何疑问的跟上文章思路。

阅读整片文章,你会发现各种各样的链接把你引向了有意思的资料,通常这些资料是在当前讨论话题领域之外的。如果你是一个在软件行业工作的程序员,那么你可能对这里面的绝大部分概念都比较熟悉。如果你是一个正在参与竞赛的年轻学生,顺着那些链接,你能发现计算机科学中其他领域的一些知识,以及你还没见过的软件工程,这将有利于扩展你的兴趣范围。

大O符号和算法复杂度分析似乎是许多程序员和年轻学生都觉得难以理解、感到害怕甚至刻意回避的东西。但它其实没有第一眼看起来那么难学,也没有那么理论化。算法复杂度只是一种用于衡量程序或者算法的运行快慢的正式方式,所以它是相当实用的。让我们从有意思一点的话题来开始。

动机

我们已经知道有些工具是用来衡量程序运行快慢的。有一种叫做性能分析器的程序,专门用来测量毫秒级的运行时间,它可以帮助我们找到程序中有缺陷的地方,从而让我们优化代码。虽然这是个很有用的工具,但是它实际上跟算法复杂度没有太大关系。算法复杂度被设计出来是用在理想情形下比较两个算法——忽略了低层次的细节,比如编程语言、算法运行的硬件以及CPU的指令集。我们希望通过算法最本质的形式来进行对比:即事物是如何计算的。计算毫秒数无法帮助我们做到这些。用类似汇编这样的低级语言写一个糟糕的算法比用PythonRuby这样的高级语言写一个优秀的算法可能要快许多。因此,是时候定义一下什么是真正的“更好的算法”。

图例1
图例1:电视游戏中的人工智能角色在虚拟世界中活动时使用了算法来躲避障碍物

算法是一些只负责运行计算的程序,而不是计算机通常会处理的网络任务或者用户输入和输出等其他工作,算法复杂度分析帮我们在一个程序执行计算的时候测量程序的快慢。这些运算的例子都是纯计算的(computational),包括数字浮点运算,例如加法和乘法;再比如在数据库中搜索一个给定的数值,并消耗合理的运行内存;给电子游戏中的人工智能角色确定一条虚拟世界中的最短路径(见图例1);或者使用正则表达式匹配一段字符串。显然,计算操作在计算机编程中无处不在。

算法复杂度分析同时是一个工具,它可以帮我们解释当输入值越来越大的时候算法是如何工作的。如果我们给定一个完全不同的输入值,算法会怎么工作?它会运行的更快,或是速度变慢一倍,或者变慢四倍?在实际的编程工作中,这是很重要的,因为它可以帮我们预测当输入的数据量变大时算法将会如何表现。例如,我给一个可容纳1000个用户并稳定运行的网络应用写一个算法,同时测量它的运行时间,使用算法复杂度分析我们就能了解到当用户量增加到2000个的时候会发生什么。对于算法竞赛,算法复杂度分析可以让我们预测到,用那些最大的试验案例检验程序的正确性时,我们的代码需要多长时间才能运行完。也就是说,如果我们能够测量程序在较小输入值时的表现,那么我们就能预测较大输入值时程序的表现。让我们从一个简单的例子开始:从数组中找到最大的元素。

指令计数

在这篇文章中,我将会用几种不同的编程语言来写例子。当然,不要因为你不了解某个编程语言而感到绝望。由于这些例子都很简单,而且我不会使用任何该语言独有的特性,只要你知道编程是什么,即使你并不熟悉这里所选的编程语言,你也应该能够无障碍的阅读这些例子。如果你是个参加编程竞赛的学生,你很可能在使用C++,那么你更应该没有问题。既然如此,我推荐使用C++来运行这些例子。

从数组中查询到最大元素可以使用很简单的代码片段来实现,类似如下的JavaScript代码。给定一个长度为n的数组A:

var M = A[0];

for (var i = 0; i < n; ++i) {
    if (A[i] >= M) {
        M = A[i];
    }
}

现在,我们要做的第一件事情是数一下这段代码执行了多少条基础指令。这种事我们只会做一次,它对于我们的理论的推进不是必须的,那么请容许我花一点时间这么做。当我们分析这段代码的时候,我们希望把它分割成一些简单的指令:即那些会被CPU直接执行或近似于被CPU直接执行的东西。我们假设处理器能够执行以下几个指令中的操作:

我们假设分支(通过 if 条件判断之后,选择 if 和 else 两个代码块中的一个)发生的非常迅速并且不包含在我们的计数里面。在上述代码中,第一行代码是:

var M = A[0];

这里需要两条指令:一个用来查找A[ 0 ],另一个用来把值赋给M(我们假设n的值至少是1),算法一般都具备这两条指令,请忽略n的值。for循环初始化代码必须是一直运行的。这样就能得到另外两条指令,赋值和比较:

i = 0;
i < n;

这些步骤会在第一次for循环迭代之前运行,我们需要另外两条指令来继续运行,一个i的增量运算和一个比较运算来检查是否继续保持在循环里面:

++i;
i < n;

因此,如果我们忽略了循环主体,这段算法需要执行的指令条数是4 + 2n条。也就是说,for循环开始之前的4条指令加上n次循环迭代中每次迭代结束时的2条。这样我们就可以定义一个数学函数f(n),即,输入n,算出这个算法需要的所有指令的总数。对于一个主体部分为空的for循环,我们需要f(n) = 4 + 2n条指令。

最坏情形分析

现在,看看for循环的主体部分,每次都会有一个数组查询操作和一个比较操作:

if ( A[ i ] >= M ) { ...

这里有两条指令,但是if的主体部分可能运行也可能不运行,这取决于数组的值是什么。如果A[ i ] >= M是成立的,那么我们会运行另外两条指令——数组查询和赋值:

M = A[ i ]

但是现在我们无法轻松的定义一个f(n)了,因为运行的指令总数不单单取决于n,同时还取决于我们输入的数据。例如,对于A = [ 1, 2, 3, 4 ],算法需要的指令总数比 A=[ 4, 3, 2, 1 ]多。当我们分析算法的时候,我们时常会考虑最坏的情形。我们的算法会发生的最坏的事情是什么?我们的算法在什么时候需要最多的指令来完成?如果是这样,我们需要的数组应该是成升序排列的,像是A = [ 1, 2, 3, 4 ]。这样,M必须每次都被替换掉,才能产生最多的指令数。计算机科学家们给这种分析方式取来了特别的名字,叫做最坏情形分析;简单来说就是考虑我们最不走运的时候的情况。那么,在最坏的情况下,我们在for循环的主体里面需要执行4条指令,即f(n) = 4 + 2n + 4n = 6n + 4。这个函数f,给它一个大小为n的问题,得到最坏情形下所需要的指令总数。

渐近行为

有了这么一个函数,我们很容易就能知道一个算法的运行快慢,然而,我敢肯定,我们不必每次都经历一遍那些冗长而乏味的基础指令的计数任务。此外,每种编程语言的语句所需要的真实的CPU指令取决于该语言所使用的编译器以及使用的CPU指令集(即你的PC上的AMD或Intel Pentium,或是你的Playstation 2上面的MIPS处理器),并且我们之前说过会忽略这些东西。我们现在通过一个“过滤器”来运行我们的“f”函数,这将会帮助我们摆脱那些不重要的细节,计算机科学家们都倾向于忽略它们。

在我们的6n + 4这个函数里,有两项:6n和4。复杂度分析里面我们只关注当输入的数据(n)变得巨大时指令计数函数将会发生什么。这正好符合前面所说的“最坏情形”分析的想法:我们感兴趣的是程序在被恶劣对待的时候的表现,特别是当它需要做一些艰难的任务的时候。注意,这对于比较两个算法是非常有用的。如果一个算法在巨量数据输入的时候打赢了另外一个算法,那么很有可能更快的那个算法在输入简单、小量的数据的时候仍然更快。在我们刚刚提到的函数项里,需要丢弃那些当n增大的时候增长速度缓慢的项,保留那些增长速度很快的项。显然,当n变大的时候,4还是4,但是6n却变得越来越大,因此在处理大型问题的时候6n就变得越来越重要了。由此可见,我们要做的第一件事就是舍弃4,然后剩下的函数将会是f(n) = 6n。

仔细想想其实是很容易理解,4只是一个“初始化常数”。不同的编程语言设置常数所需要的时间可能有所不同,例如,Java需要一些时间来初始化虚拟机。由于我们忽略了编程语言之间的区别,那么忽略这个值也是没有问题的。

第二个我们需要忽略的是n前面的乘法因子的常数,那么我们的函数就变成了f(n) = n。你可以看到,现在事情变得简单多了。同样的,如果我们考虑到编程语言之间的区别,那么丢弃这个乘法因子常数也是能够理解的。“数组查询”语句在不同的编程语言里面可能会编译成不同的指令。例如,在C里面,用A[ i ]取值不需要检查i是否在数组的长度范围内,而在Pascal里却是需要的。那么,以下的Pascal代码:

M := A[ i ]

等价于以下的C代码:

if ( i >= 0 && i < n ) {
    M = A[ i ];
}

所以说我们提前预测到在记录指令数量时不同编程语言将会受到不同因素的影响是很合理的。在上面的例子中,我们使用了一个基本不可能优化的Pascal的拙劣的编译器,Pascal每次访问数组数据需要3条指令,而在C里面只需要1条指令。丢弃这些因素正好符合我们的原则,即:忽略具体的编程语言和编译器之间的差异,只分析算法的思想本身。

上面介绍的“丢弃所有因子”并“保留最大增长项”的过滤方式就是我们所说的渐进行为。那么f(n) = 2n + 8 的渐进行为可以描述为函数 f(n) = n。用数学上的说法,我们真正感兴趣的是当n趋近于无穷大的时候函数f的极限;如果你不理解这个的句子的正式含义,别着急,你需要了解的东西都跟这个有关。(特别说明一下,在严格的数学情境里,我们不能丢弃极限里面的常量;但是在计算机科学中,基于上文描述的原因,我们必须这么做。)让我们通过几个例子来熟悉一下相关概念。

让我们通过丢弃常数因子并保留增长最快的项的方式来找到下列函数的渐进行为。

  1. $ f( n ) = 5n + 12 $ 变成 $ f( n ) = n $。 基于上文中提到的相同的原因。

  2. $ f( n ) = 109 $ 变成 $ f( n ) = 1 $。 我们丢弃了乘法因子$ 109 * 1 $,但是我们仍然需要放一个1在这里以表示这个函数的值是非零数。

  3. $ f( n ) = n^2 + 3n + 112 $ 变成 $ f( n ) = n^2 $。 这里,当n足够大的时候,$ n^2 $比$ 3n $大的多,所以我们保留了前者。

  4. $ f( n ) = n^3 + 1999n + 1337 $ 变成 $ f( n ) = n^3 $。 即使n前面的因子比较大,我们还是能够找到一个足够大的n使得$ n^3 $比$ 1999n $大。由于我们只对$ n$ 非常大的时候的情形感兴趣,所以我们只保留了$ n^3 $(见图例2)。

  5. $ f( n ) = n + \sqrt{n} $变成$ f( n ) = n $。 这是因为当$ n $增加的时候$ n $比$ \sqrt{n} $的增长快的多。

图例2
图例2:在$ n = 45 $之后,$ n^3 $函数(蓝色)变得比$ 1999n $函数(红色)大,而且过了这个点之后将会一直更大。

你也可以自己尝试以下例子:

练习1

  1. $ f( n ) = n^6 + 3n $
  2. $ f( n ) = 2^n + 12 $
  3. $ f( n ) = 3^n + 2^n $
  4. $ f( n ) = n^n + n $

(写下你的结果;答案将会在下文给出)

如果你在解答上面某一题时感到困难,不妨代入一个数值较大的$ n $进去,然后看看哪一项更大就行了。相当简单直接,是吧?


复杂度

这就告诉我们,由于舍弃了所有装饰性的常数,很容易就能说出一个程序的指令计数函数的渐进行为。事实上,任何一个不包含循环的程序的指令计数函数都是$ f( n ) = 1 $,因为指令的条数仅仅需要一个常数而已(除非这个程序使用了递归,下文会提到)。任何包含了一个从1到n的循环的程序的指令计数函数是$ f( n ) = n $,因为它会在循环之前执行固定数量指令,循环之后执行固定数量的指令,以及循环里面将会运行n次相同数量的指令。

现在这种方式比一个一个的数所有指令条数的方式要轻松有趣的多,让我们看几个例子来熟悉一下这种方式。以下PHP程序用来检测一个具体的值是否存在于长度为n的数组A里面:

<?php
    $exists = false;
    for ( $i = 0; $i < n; ++$i ) {
        if ( $A[ $i ] == $value ) {
            $exists = true;
            break;
        }
    }
?>

这种从一个数组里面搜索某个值的方法叫做线性搜索。这是一个很恰当的名字,因为这个程序的渐进函数为$ f( n ) = n $(在下一部分中我们将会详细的定义“线性”的含义)。你可能注意到有个“break”语句可以让程序很快终止,即使只迭代了一次。但是别忘了我们只对最坏情形感兴趣,也就是说数组A里面根本不包含这个值。所以我们依然有函数$ f( n ) = n $。

练习2

有条不紊的分析以上PHP程序在最坏情形下所需的指令条数,从而找到函数$ f( n ) $,用类似于我们分析过的第一个JavaScript程序那样的方式。验证一下,渐渐的,我们会得到 $ f( n ) = n $。


让我们看看这样一个Python程序,把两个数组的元素相加,得到的值存储在另一个变量里面:

v = a[ 0 ] + a[ 1 ]

这里我们需要一个固定数量的指令,所以会得到 $ f( n ) = 1 $。

以下C++程序是用来检测一个长度为n名为A的向量(一种奇特的数组)里面是否包含两个相同的值:

bool duplicate = false;
for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j ) {
        if ( i != j && A[ i ] == A[ j ] ) {
            duplicate = true;
            break;
        }
    }
    if ( duplicate ) {
        break;
    }
}

由于这里有两个相互嵌套的循环,我们会得到一个$ f( n ) = n^2 $的渐进行为。

经验法则:分析一个简单的程序只需要数一下程序里面嵌套的循环的数量即可。只有一个遍历了n项的循环将会得到$ f( n ) = n $。一个循环里面有一个循环将会得到$ f( n ) = n^2 $。一个循环里面有一个循环,最里面还有一个循环,将会得到$ f( n ) = n ^3 $。

如果我们有一个程序在循环里面调用了一个函数,而且我们知道这个函数执行的指令条数,那么我们就很容易确定整个程序的指令总数。这是毫无疑问的,让我们来看看这一段C代码:

int i;
for ( i = 0; i < n; ++i ) {
    f( n );
}

如果我们知道 f( n ) 是一个正好执行了n条指令的函数,由于这个函数被调用了n次,那么我们就能确定整个程序执行的指令总数接近于$ n^2 $。

经验法则:给定一系列连续的for循环,最慢的那个将会决定程序的渐进行为。两个相互嵌套的循环后面跟着一个非嵌套的循环相当于只有两个相互嵌套的循环,因为相互嵌套的循环相比简单的循环更具主导地位。

现在,让我们转换到计算机科学家们使用的奇特符号。当我们渐渐的弄明白了f函数,我们会说我们的程序是$ \Theta( f( n ) ) $。例如,上文中的程序分别是$ \Theta( 1 ) $、$ \Theta( n^2 ) $、$ \Theta( n ) $。$ \Theta( n ) $应该读作“n的theta”。有时候我们会说一个函数$ f( n ) $是$ \Theta( … ) $,原函数是用来计算指令条数的,并且包含了常量。例如,我们会说$ f( n ) = 2n $这个函数是$ \Theta( n ) $——这没有什么新奇的。我们也可以写成$ 2n \in \Theta( n ) $,读作“2n是n的theta”。不要因为这个符号感到迷惑:它表达的含义是,如果我们计算得出一个程序所需要的指令数量是2n,那么通过舍弃常量,我们的算法的渐进行为被描述为n。使用这个符号,我们就有了一些成立的数学语句:

  1. $ n^6 + 3n \in \Theta( n^6 ) $
  2. $ 2^n + 12 \in \Theta( 2^n ) $
  3. $ 3^n + 2^n \in \Theta( 3^n ) $
  4. $ n^n + n \in \Theta( n^n ) $

顺便说明一下,如果你解决了上面的练习1,那么在这里你应该正好能找到一些答案

我们把放在$ \Theta( … ) $括号里面的函数叫做时间复杂度,或者直接叫做算法的复杂度。所以一个$ \Theta( n ) $的算法相当于复杂度为n。我们也给$ \Theta( 1 ) $、$ \Theta( n^2 ) $、$ \Theta( n ) $分别起了特殊的名字,因为它们经常会被用到。我们把一个$ \Theta( 1 ) $算法叫做常数时间算法,$ \Theta( n ) $叫做线性,$ \Theta( n^2 ) $叫做二次方,$ \Theta( log( n ) ) $叫做对数(不要担心你还不了解对数是什么,我们一会儿就会讲到这里)。

经验法则:一个$ \Theta $数值较大的程序比一个$ \Theta $数值较小的程序运行的更慢一些。

大O符号

现在,你不得不承认,使用上面提到的方法有时候并不能搞清楚一个算法的具体表现,特别是在处理更复杂的案例的时候。然而,我们可以知道算法的行为表现不会超出某个特定的边界。这让我们活的轻松一点,因为我们并不一定要精确的指出算法运行的有多快,即便是用上文提到的方法忽略了常数。我们要做的只是找到这个特定的边界。用一个例子就很好解释了。

图例3
图例3:位于黄点位置的玩家将无法看到阴影区域。把虚拟世界分割成很小的碎片,然后根据它们到玩家的距离来给它们排序,这是用来解决可见性问题的方案之一。

排序问题是计算机科学家们在传授算法知识时经常用到的一些著名问题。在排序问题里,给定一个长度为n名为A的数组(听起来很熟悉是吧?),然后我们需要写一个程序给这个数组里的元素排序。这个问题很有趣,因为它是在真实系统中会出现的一个问题。比如,为了让用户更好的操作文件管理器里面的文件,我们需要根据文件名给它们排序。又比如,电子游戏需要给正在显示的3D对象进行排序,基于它们从玩家的眼睛到虚拟世界里面的距离,从而决定哪些是可见哪些是不可见的,这就是所谓的可见性问题(见图例3)。最终,那些离玩家最近的对象是可见的,离玩家较远的对象会被它们前面的对象遮挡住从而保持隐藏状态。排序是个很有意思的例子,因为有许多算法专门用来解决这个问题,而且它们相互之间又优劣的差别。它同时也是一个很容易定义和解释的问题。那么让我们来写一段代码来给数组排序。

这里用Ruby写来一个比较低效的方法来实现来给数组排序。(当然,Ruby提供来内建函数来给数组排序,平时写代码你应该使用它,而且内建函数比我们这里看到的方法快得多,这里的代码主要用来作为示例而已。)

b = []
n.times do
    m = a[ 0 ]
    mi = 0
    a.each_with_index do |element, i|
        if element < m
            m = element
            mi = i
        end
    end
    a.delete_at( mi )
    b << m
end

这种方法叫做选择排序。它找到数组里面最小的一项(数组用上面的a来表示,最小值用m来表示,mi是最小值的索引),把它放到新数组(例子里面的b)的末尾,然后从原数组里面删掉最小项。然后又从原数组剩余的值里面找到最小的一个,将其添加到新数组的末尾,这时候新数组包含两个元素了,然后从原数组删除这个最小项。以此类推,直到原数组里面的元素都被删除,并且都被插入都新数组里面,这就相当于数组被排序了。在这个例子里面我们可以看到又两个嵌套着的循环。外层的循环运行了n次,内层的循环给数组a的每个元素都运行了一次。数组a在最开始的时候有n个元素,我们在每次迭代里面都会去掉一个。那么在第一次迭代里内层循环重复运行了n次,然后是n-1次,然后是n-2次,以此类推,直到外层循环进行最后一次迭代时它只运行一次。

要弄清楚这个程序的复杂度有点困难,因为我们需要算出1 + 2 + … + (n - 1) + n。但是毫无疑问我们能给它找到一个“上边界”。也就是说,我们可以修改我们的程序(你可以在想象中这么做,而不是修改实际的代码)让它变得比现在更糟糕,这样我们就能找到派生出来的新程序的复杂度。如果可以找到我们创建的新程序的复杂度,那么我们就能知道原程序在最坏的情形下可能比这个还要好一点。同样的,如果我们从派生的程序里面发现了一个比原程序糟糕但是稍微好一点的复杂度,那么我们就能知道原程序也有一个稍微好一点的复杂度——同派生出来的程序一样好,而且可能更好一点。

为了更容易找到例子中的程序的复杂度,让我想一下该怎么修改这个程序比较好。一定要记住,我们只需要让程序变得更糟糕,即让它需要运行更多的指令,这样我们对原程序的评估才有意义。显然,我们可以修改程序内层的循环,让它一直都重复执行n次而不是每次都运行不同的次数。有些重复迭代可能是无用的,但有助于我们分析算法的复杂度。如果我们做了这个简单的修改,那么创建的新的算法的显示应该是$ \Theta( n^2 ) $,因为程序里面又两个相互嵌套的循环,且每个循环都会迭代n次。如果是这样,那么我们就说原算法是$ O( n^2 ) $。$ O( n^2 ) $读作“n的二次方的大o”。它表达的是我们的程序的渐进行为不可能比$ n^2 $更糟糕了,只可能比$ n^2 $好或者正好就是$ n^2 $。顺便说下,如果我们的程序确实是$ \Theta( n^2 ) $,那么我们依然可以说它是$ O( n^2 ) $。为了帮你认识到这一点,可以想象一下对原程序做一些细微的修改,但是可以让程序变得糟糕一点,比如在程序的头部添加一条无意义的指令。这么做相当于修改了程序的指令计数函数里面的一个常数,而这个常数在分析渐进行为的时候会被忽略掉。所以一个$ \Theta( n^2 ) $程序相当于一个$ O( n^2 ) $程序。

然而一个$ O( n^2 ) $程序未必是一个$ \Theta( n^2 ) $。例如,任何一个$ \Theta( n ) $程序相当于$ O( n^2 ) $去掉了$ O( n ) $。如果我们想象$ \Theta( n ) $程序就是一个简单的重复n次的for循环,我们可以在它的外面套另外一层重复n次的for循环,从而让程序变得更糟糕,那么得到的程序将会是$ f( n ) = n^2 $。概括一下就是,对任何程序而言,当b比a更糟糕的时候,$ \Theta( a ) $就是$ O( b ) $。需要注意的是,我们修改程序的时候并不需要得到一个实际中有意义的程序或者跟原程序一样的程序。它仅仅只需要在输入n的时候比原程序执行更多的指令就行。我们仅仅用它来计算指令条数,而不是用来解决实际中的难题。

那么,说一个程序是$ O( n^2 ) $是一种可靠的说法:我们已经分析过算法,并且发现它不可能比$ n^2 $更糟糕。当然它可以正好是$ n^2 $。这就让我们能够很轻松的评估一个程序的运行快慢。让我们通过几个例子来帮助你熟悉一下这个新符号。

练习3

找到以下句子哪些是成立的:

  1. 一个$ \Theta( n ) $算法相当于$ O( n ) $
  2. 一个$ \Theta( n ) $算法相当于$ O( n^2 ) $
  3. 一个$ \Theta( n^2 ) $算法相当于$ O( n^3 ) $
  4. 一个$ \Theta( n ) $算法相当于$ O( 1 ) $
  5. 一个$ O( 1 ) $算法相当于$ \Theta( 1 ) $
  6. 一个$ O( n ) $算法相当于$ \Theta( 1 ) $

解答

  1. 这个句子是成立的,由于原函数是$ \Theta( n ) $,我们完全不需要修改程序就能得到$ O( n ) $。
  2. $ n^2 $比$ n $糟糕,所以成立。
  3. $ n^3 $比$ n^2 $糟糕,所以成立。
  4. 由于$ 1 $并不比$ n $糟糕,所以不成立。如果一个程序需要约n条指令(一个线性的指令条数),我们无法让它变等更糟糕以至于只有约一条指令(一个恒定的指令条数)。
  5. 成立,因为两个复杂度是一样的。
  6. 这个有可能成立也有可能不成立,主要取决于算法。大部分情况下是错误的。如果一个算法是$ \Theta( 1 ) $,那么可以确认它是$ O( n ) $。但是一个$ O( n ) $并不一定是$ \Theta( 1 ) $。比如,一个$ \Theta( n ) $算法是$ O( n ) $但是却不是$ \Theta( 1 ) $。

练习4

用等差级数求和来证明上文中提到的,如果一个程序是$ O( n^2 ) $,那么它一定也是$ \Theta( n^2 ) $。如果你不知道等差级数是什么,可以在维基百科上查查看——这很简单。


由于O复杂度代表的是一个算法的实际复杂度的上边界,而$ \Theta $代表的是一个算法的实际复杂度,有时候我们会说$ \Theta $代表的是紧密边界。如果我们推导的复杂度边界不那么紧密,我们依然可以用用一个小写的o来表示它。比如说,一个算法是$ \Theta( n ) $,那么它的紧密复杂度就是$n$。如果一个算法同时是$ O( n ) $ 和 $ O( n^2 ) $,由于算法是$ \Theta(n) $,所以$ O( n ) $是紧密的那一个。但是由于$ O( n^2 ) $不是紧密的,我们可以写成算法是$ o( n^2 ) $,读作“n的二次方的小o”,这样就能表明该边界不是紧密的。如果我们能找到算法的紧密边界那就更好了,因为这样我们就能知道更多关于算法的行为信息,虽然并不那么好找。

练习5

确定以下边界哪些是紧密边界哪些不是紧密边界。检查是否有错误的边界。使用o( 符号 )来表示该边界是不紧密的。

  1. 一个$ \Theta( n ) $算法的上边界是$ O( n ) $
  2. 一个$ \Theta( n^2 ) $算法的上边界是$ O( n^3 ) $
  3. 一个$ \Theta( 1 ) $算法的上边界是$ O( n ) $
  4. 一个$ \Theta( n ) $算法的上边界是$ O( 1 ) $
  5. 一个$ \Theta( n ) $算法的上边界是$ O( 2n ) $

答案

  1. 在这个例子里,$ \Theta $复杂度和$ O $复杂度是一样的,所以该边界是紧密的。
  2. 这里我们可以看到$ O $复杂度的范围比$ \Theta $复杂度更大,所以这个边界不是紧密的。事实上,$ O( n^2 ) $才是紧密边界。那么我们可以写作该算法是$ o( n^3 ) $。
  3. 同样我们可以看到$ O $复杂度比$ \Theta $复杂度的范围大,所以这不是一个紧密边界。$ O( 1 ) $才是紧密边界。那么我们就能指出$ O( n ) $不是紧密的,应该写成$ o( n ) $。
  4. 如果我们计算这里的边界那么肯定会有问题,因为它本身就是错误的。一个$ \Theta( n ) $算法不可能有一个$ O( 1 ) $这样的上边界,因为$n$这个复杂度比$1$更大。记住,O代表的是上边界。
  5. 这个可能看起来是一个不紧密的边界,事实上并不是这样。这个边界实际上是紧密的。你应该记得渐进行为里面的2n跟n是一样的,而$ O $和$ \Theta $也只关心渐进行为。那么我们有$ O( 2n ) = O( n ) $,可以看到该复杂度跟$ \Theta $是一样的,所以这个边界是紧密的。

经验法则:找出$ O $复杂度比找出$ \Theta $复杂度要容易一些。

你可能对这些新的符号感到有压力,在进入新的例子之前让我们再介绍两个新的符号。当你了解了$ \Theta $、$ O $以及$ o $之后再学习这两个符号就变得轻松多了,而且我们在后面的文字里面也不会使用太多,但是了解一下它们也还是不错的。在上面的例子中,我们修改程序以使得它变得更糟糕(即执行更多的指令从而花费更多的时间),并且我们创造了$ O $符号。$O$是很有意义的,因为它告诉我们程序不可能比某个具体的边界更慢了,而且它提供了一个可估量的信息让我们可以证明我们的程序写的足够好了。如果我们使用相反的方式来修改程序,让程序变得更好并找到派生程序的复杂度,我们用$\Omega$符号来表示。因此$\Omega$代表的是我们的程序不可能比它更好的一个复杂度。如果我们想证明一个程序或者一个算法是糟糕的,它将会很有用。它同样可以用于证明一个算法在某个具体的案例中使用将会非常慢以至于程序不能运行。例如,我们说一个算法是$\Omega(n^3)$,即代表这个算法不可能比$n^3$更好。它可能是$\Theta(n^3)$,可能像$\Theta(n^4)$一样糟糕,或者更糟,但我们知道它至少是有那么点差劲。所以$\Omega$代表的是算法的复杂的下边界。跟$o$类似,如果边界不是那么紧密我们就把它写作$\omega$,$\omega(n)$读作“n的小$\omega$”。

练习6

给以下$\Theta$复杂度写下一个紧密和一个非紧密的$O$边界,以及一个紧密和一个非紧密的$\Omega$边界。

  1. $\Theta(1)$
  2. $\Theta(\sqrt n)$
  3. $\Theta(n)$
  4. $\Theta(n^2)$
  5. $ \Theta(n^3)$

答案

这个例子是对上文介绍的一些定义的简单直接的应用

  1. 紧密边界是$O(1)$和$\Omega(1)$。非紧密O边界是$O(n)$。记住,$O$代表的是上边界。而且$n$比$1$的规模大一些所以是一个非紧密边界,我们可以写成$o(n)$。但是我们无法找到一个非紧密的$\Omega$边界,因为我们无法找到一个比$1$更低阶的函数了。
  2. 紧密边界应该跟$\Theta$复杂度是相同的,所以分别应该是$O(\sqrt n)$和$\Omega(\sqrt n)$。对于非紧密边界,应该是$O(n)$,因为$n$比$\sqrt n$大,所以它是个上边界。由于这是个非紧密的上边界,所以可以写作$o(n)$。对于一个不紧密的下边界,我们可以用$\Omega(1)$。由于这个边界是非紧密的,我们也可以写成$\omega(1)$。
  3. 紧密边界分别是$O(n)$和$\Omega(n)$。两个非紧密边界可以是$\omega(1)$和$o(n^3)$。其实这两个是比较糟糕的边界,因为它们跟原来的复杂度相去甚远,但它们依然符合我们的定义。
  4. 紧密边界分别是$O(n^2)$和$\Omega(n)$。两个非紧密边界依然可以使用跟前一个例子相同的$\omega(1)$和$o(n^3)$。
  5. 紧密边界分别是$O(n^3)$和$\Omega(n^3)$。两个非紧密边界分别是$\omega(\sqrt n n^2)$和$o(\sqrt n n^3)$。虽然这两个边界也不是紧密的,但是比前面例子中给出的要好一些。

即使$O$和$\Omega$也有紧密边界,我们依然使用$O$和$\Omega$而不使用$\Theta$,这是因为我们无法说明找到的边界是否是紧密的,或者说我们只是不想经历一遍整个处理过程。

如果你现在还无法完全的记住所有符号以及它们的用法,别太担心。你可以随时回来查看,最重要的两个符号是$O$和$\Theta$。

注意虽然$\Omega$代表的是函数下边界的表现(相当于提升了程序的性能让其执行更少的指令),我们依然是指“最坏情形”的分析。这是因为我们向程序中输入了尽可能糟糕的数据n并分析程序在此情形下的表现。

以下表格显示了我们刚刚介绍的符号,以及它们与数字运算时常用的符号的比较。我们使用希腊字母而不使用常用的数学符号的原因是我们做的是渐进行为对比,而不是简单的数学对比。

渐进行为对比操作 数字对比操作
算法是$o(…)$ 一个数字 $<$ …
算法是$O(…)$ 一个数字 $\le$ …
算法是$\Theta(…)$ 一个数字 $=$ …
算法是$\Omega(…)$ 一个数字 $\ge$ …
算法是$\omega(…)$ 一个数字 $>$ …

经验法则:$O$、$o$、$\Omega$、$\omega$以及$\Theta$都是时常用到的符号,其中$O$使用的更广泛一些,因为它比$\Theta$更好确定同时又比$\Omega$更加实用。

对数

图例4
图例4:$n$、$\sqrt n$、$log(n)$三个函数的对比。函数$n$是线性函数,最上面的用绿线画的那个,跟平方根函数相比增长的更快。平方跟函数是中间用红线画的那个,跟最下面的蓝色线条画的$log(n)$函数相比,增长速度更快。即使对于一个数值较小的n,例如n=100,差异还是很明显。

如果你已经知道对数是什么了,那么可以跳过这以部分。由于很多人不熟悉对数或者最近没怎么使用导致不记得了,这一节将做一个介绍。这些文字也是为那些在学校还没学习对数的年轻学生们而准备的。对数还是比较重要的,因为在分析复杂度的时候经常会出现。对数就是一个让数字变小的操作——有点像数字的平方根。所以,关于对数你需要记住的是,它带有一个数字,并且让原数字的值变得小很多(见图例4)。就像平方根是某个数字的平方的反向操作一样,对数是某个数字的幂的反向操作。这并没有听起来那么难。用一个例子来解释就好懂了。思考下面的等式:

$2^x = 1024$

我们现在希望解出等式中的x。那么我们要问自己:我们需要什么数字才提升基数2的值得到1024?很明显答案是10。确实,$2^{10} = 1024$,这很容易验证。对数帮我们用一种新的符号来表示这种问题。在这个例子里面,10是1024的对数,写作$log(1024)$,读作“1024的对数”。由于我们用2作为基数,这些对数被称作基于2的对数。当然也有基于其他数字的对数,但是在这篇文章里面我们只使用基于基于2的对数。如果你是参与国际竞赛的学生同时你还不了解对数,我强烈推荐你在读完此文后练习对数运算。在计算机科学里面,基于2的对数比其他类型的对数更常见。这是因为我们经常只有两个字符实体:0和1。我们倾向于把大问题分成几个部分,通常是两部分。所以你只需要了解基于2的对数来继续阅读此文。

练习7

解出以下等式。写出你从每个例子里面找到的对数。使用基于2的对数即可。

  1. $2^x = 64$
  2. $(2^2)^x = 64$
  3. $4^x = 4$
  4. $2^x = 1$
  5. $2^x + 2^x = 32$
  6. $(2^x)*(2^x) = 64$

答案

  1. 通过几次尝试我们可以知道x = 6,所以$log(64) = 6$。
  2. 根据指数计算的特性,我们可以把$(2^2)^x$写成$2^{2x}$。根据前一个例子的$log(64) = 6$我们可以知道2x = 6,所以x = 3。
  3. 根据前面的例子用到的知识,我们可以把4写成$2^2$,所以等式就变成了$(2^2)^x = 4$,相当于$2^{2x} = 4$。那么我们可以知道$log(4) = 2$因为$2^2=4$,因此2x = 2,所以x = 1。由于使用了一个1作为指数同时基数作为结果,通过原等式还是很容易看出来的。
  4. 记得指数是0的时候得到的结果是1。所以我们有$log(1)=0$因为$2^0=1$,所以x = 0。
  5. 由于这里有求和运算所以我们无法直接使用对数。然而我们注意到$2^x + 2^x$相当于$2 * 2^x$。相当于我们乘以另外一个2,即$2^{x+1}$,所以我们要解的等式是$2{x+1}=32$。我们找到$log(32) = 5$所以x+1 = 5,因此x = 4。
  6. 我们把两个2的幂数相乘,可以把它们结合倒一起,所以$(2^x) * (2^x)$相当于$2^{2x}$。所以我们只需要解出等式$2^{2x} = 64$即可,通过上面的例子可以知道x = 3。

经验法则:对于用C++实现的竞赛算法,一旦你分析算法复杂度,你将很难通过每秒执行1000000次操作的方式来评估程序的运行的快慢,你计数的那些操作是由算法的渐进行为函数来决定的。例如,一个$\Theta(n)$算法需要花费一秒钟来处理输入值为n = 1000000的数据。

递归复杂度

现在我们来看看递归函数。一个递归函数即一个调用自身的函数。我们能分析它的复杂度么?下面用Python写的函数来计算给定数字的阶乘。一个正整数的阶乘是通过把它之前的所有正整数相乘而得来。例如,5的阶乘就是$54321$。我们一般用“5!”来表示,读作“5的阶乘”(有些人喜欢这样读:大声的喊“5!!!”)。

def factorial( n ):
    if n == 1:
        return 1
    return n * factorial( n - 1 )

让我们分析一下这个函数的复杂度。这个函数里面不包含循环,但是它的复杂度也不是常数。我们又要通过数指令的方式来找到它的复杂度了。显然,我们给函数传了一个n,那么它会执行自己n次。如果你还不那么确定,可以通过用手数数的方式来验证,数一下当n=5的时候它实际执行的次数。例如,对于n=5,他会执行5次,因为他会在每次执行的时候减少1。因此我们可以看到这个函数就是$\Theta(n)$。

如果你还是不那么确定,只需记得你随时可以通过数指令数的方式来找到准确的复杂度。只要你愿意,你可以数一下这个函数实际执行的指令条数,你会发现函数$f(n)$并且看到它确实是线性的(记住,线性是指$\Theta(n)$)。

图例5,这个图可以帮助你理解当调用factorial( 5 )的时候执行了哪些递归。

图例5
图例5:阶乘函数执行的递归

这也能解释清楚为什么这个函数是线性复杂度。

对数复杂度

计算机科学中一个著名的问题就是从数组里面找到某个值。我们之前通过一般的例子解决了这类问题。如果我们有一个已排序的数组同时又要找到某个特定的值,那么问题就变得有趣了。有一种方法叫做二分搜索。我们只需找到数组里排在最中间的元素即可:如果找到了,那么排序就完成了。否则,如果找到的值比目标值大一些,我们就知道目标元素应该在数组的左半部分,如果相反,这个元素就应该在右半部分。我们可以一直把那些较小的数组分成两部分直到数组只剩下一个元素。这里是用来实现的伪代码:

def binarySearch( A, n, value ):
    if n = 1:
        if A[ 0 ] = value:
            return true
        else:
            return false
    if value < A[ n / 2 ]:
        return binarySearch( A[ 0...( n / 2 - 1 ) ], n / 2 - 1, value )
    else if value > A[ n / 2 ]:
        return binarySearch( A[ ( n / 2 + 1 )...n ], n / 2 - 1, value )
    else:
        return true

这个伪代码是实际代码的简化版。在实际中,这个方法描述起来比代码实现容易得多,作为程序员,应该注意到一些代码实现相关的细节问题。代码中有差一错误,而且用2作为除数不一定能得到整数值,所以这里需要floor()或者ceil()来处理一下。但是我们假设代码总是成功运行的,假设实现过程中我们照顾到了差一错误问题,我们只是为了分析这个方法的复杂度而已。如果你之前从来没有实现过二分搜索算法,你可以用你最喜欢的语言写一个试试,这将让你感到很有启发性。

图例6能够帮你理解二分搜索的操作方式。

图例6
图例6:二分搜索执行的递归。每次调用时的参数A使用黑色高亮。递归持续到数组只由一个元素构成为止。来自Luke Francl。

如果你还是不确定这个方法实际是怎么运行的,现在来花点时间手动运行一个简单的例子,直到你真正弄懂了为止。

让我们试着分析一下这个算法。首先,例子里面有一个递归算法。为了简单化,我们假设数组总是能够对半分,忽略递归过程中的+1和-1部分。现在你应该知道,一些小的改变,例如忽略了+1和-1部分,将不会影响到复杂度分析的结果。如果我们想要从数学的立场上表现的更严谨一些,那么就必须证明这个事实,事实上它是非常直观而又明显的。我们假设数组的长度正好是2的倍数,这个假设仍然不会改变我们最终得到的复杂度的结果。当我们找的值根本不存在数组当中的时候,相当于这个问题出现了最坏情形。在那个例子里面,我们在第一次递归的调用里面使用了一个长度为n的数组,然后在下一次递归调用里面得到一个长度为n / 2的数组。在下一次的调用里面得到长度为n / 4的数组,在随后的调用里面得到n / 8的数组,以此类推。总之,数组在每次递归调用里面都会被对半分,直到数组长度为1。那么,让我们写下每次调用时的数组里面的元素的个数:

  1. 第0次迭代:$n$
  2. 第1次迭代:$n / 2$
  3. 第2次迭代:$n / 3$
  4. 第3次迭代:$n / 4$ … 第i次迭代:$n / 2^i$ … 最后一次迭代:$1$

可以看到第i次迭代时,数组里面有$n/2^i$个元素。这是因为每次迭代我们都把数组切成两半,也就是将元素的个数处以2,即相当于把分母乘以2。如果像这样操作了i次,就会得到$n/2^i$。这个过程持续进行,每次i变大一些我们就会得到数量更小的元素,直到最后一次迭代时只剩下1个元素。如果我们希望找到i来确定这是那一次迭代,那么需要解出以下等式:

$1 = n / 2^i$

只有当binarySearch()函数的最后一次调用发生时这个等式才成立,这不是一个一般情况。因此解出了这里的i就能帮我们找到递归会在哪次迭代的时候执行完。给等式两边同时乘以$2^i$可以得到:

$2^i = n$

现在,如果你阅读了上面的对数部分你会发现这个等数比较眼熟。可以解出i的值:

$i = log(n)$

这就告诉我们执行一个二分搜索所需要的迭代数量是$log(n)$,其中n是原数组中元素的个数。

如果你稍微思考一下,就很容易说得通了。举个例子:取n = 32,一个包含32个元素的数组。我们需要将数组对半切分多少次才能得到只有一个元素的数组?我们会这么做:32 → 16 → 8 → 4 → 2 → 1。一共做了5次,这个数字正好是32的对数。因此,二分搜索算法的复杂度是$\Theta(log(n))$。

这个最终结果允许我们将二分搜索跟之前的线性搜索进行对比。显然,$log(n)$比$n$小的多,这就可以推断使用二分搜索查找数组中的元素比线性搜索快一些,这也是用来给数组排序时的建议,特别是当需要在数组内进行多次搜索的时候。

经验法则:改善一个程序的渐近运行时间通常能够惊人的提高程序的性能,这比一些小的“技巧性”的优化要强的多,比如换一个快一点的编程语言。

最优排序算法

恭喜你。你已经知道了算法复杂度的分析过程,函数的渐进行为以及大O符号。你也知道了如何直观的找到一个算法的复杂度是$O(1)$、$O(log(n))$、$O(n)$或者$O(n^2)$等等。你知道了$o$、$O$、$\omega$、$\Omega$和$\Theta$这些符号以及最坏情形分析的意思。如果你学到了这里,这篇教学的目的就达到了。

最后这一部分是可选的。它稍微有点复杂,如果你感觉阅读起来有压力的话可以选择跳过。阅读这一部分需要专注,同时需要你花点时间完成练习题。当然,它将提供一种强大而有用的算法复杂度分析方法,所以这一部分是很值得去学习并理解。

我们来看看上面的选择排序的实现。我们提到过,选择排序并不理想。一个最优算法即一个可以用最好的方式来解决问题的算法,也就是说不会有比这个更好的算法了。那些用于解决此问题的其他算法都有一个比最优算法的复杂度更糟或者一样的复杂度。同一个问题可能会有多个最优算法,并且有着相同的复杂度。排序问题可以用多种方式理想化的解决。我们可以使用跟二分搜索一样的思维方式来实现快速的排序。这种方法叫做归并排序

要执行一个归并排序,首先要建立一个辅助函数,之后会用它来做实际的排序。我们建一个merge函数,用来将两个已经排序的数组合并成一个大的排序过的数组。这很容易做到:

def merge( A, B ):
    if empty( A ):
        return B
    if empty( B ):
        return A
    if A[ 0 ] < B[ 0 ]:
        return concat( A[ 0 ], merge( A[ 1...A_n ], B ) )
    else:
        return concat( B[ 0 ], merge( A, B[ 1...B_n ] ) )

这个合并函数携带了一个“头部”和一个“尾部”(数组),并且把他们结合起来返回一个新的数组,新数组把“头部”作为第一项,把“尾部”作为其他项。例如,concat(3, [4, 5, 6]) 返回 [3, 4, 5, 6]。我们分别用 A_n 和 B_n 来表示数组A和数组B的长度。

练习8

确认以上函数确实执行了一次合并。用你最喜欢的编程语言重写一下,使用迭代的方式(用for循环)而不是递归。


分析这个算法可以知道它的运行时间为$\Theta(n)$,其中n是最终得到的数组的长度(n = A_n + B_n)。

练习9

证实merge函数的运行时间是$\Theta(n)$


利用这个函数我们可以建造一个更好的排序算法。思路是这样的:把一个数组分成两部分。分别给这两部分递归的排序,然后把两个已排序的算法何合并到一个大的数组里面。伪代码如下:

def mergeSort( A, n ):
    if n = 1:
        return A # 这个数组已经被排序过了
    middle = floor( n / 2 )
    leftHalf = A[ 1...middle ]
    rightHalf = A[ ( middle + 1 )...n ]
    return merge( mergeSort( leftHalf, middle ), mergeSort( rightHalf, n - middle ) )

这个函数相比我们之前学习的函数要难以理解一些,因此接下来的练习需要花费你一些时间。

练习10

证实mergeSort函数的正确性。即,检查上面定义的mergeSort是否正确的给数组排序了。如果你对它的运作原理不是很理解,可以尝试输入一个小点的数组,然后“手动”运行这个函数。当你手动运行这个函数的时候,请确认leftHalf和rightHalf都是通过把数组从中间切开而得到的;如果数组含有奇数个元素,你不需要精确的算出中间的位置(这就是为什么上面要使用floor函数)。


作为一个最终的例子,让我们来分析一下mergeSort的复杂度。在mergeSort执行的每一个步骤里,我们把数组分成大小相同的两半,这跟binarySearch类似。然而,在这个例子里面,我们对所有的半边数组都进行了遍历操作。然后我们又对每个半边数组递归执行了这个算法。递归操作返回之后,我们对结果执行了merge操作,这将花费$\Theta(n)$的运行时间。

因此,我们每次都把原数组分成两个n/2长度的数组。然后再合并这些数组,合并n个元素的操作花费了$\Theta(n)$的时间。

看一看图例7来理解这个递归。

图例7
图例7:归并排序的递归树。

让我们来看看发生了什么。每一个圆圈表示执行了一次mergeSort函数。圆圈里面的数字代表的是正在被排序的数组的长度。顶部的蓝色圆圈是最原始的mergeSort的调用,也就是我用于给长度为n的数组排序的地方。箭头表示的是函数之间发生的递归调用。原始的mergeSort的调用创造了两个长度为n/2的数组上的mergeSort的调用。顶部的两个箭头表示的就是这个过程。紧接着,这里面的每一个函数调用又制造了两个长度为n/4的数组上的mergeSort调用,依照这个规律一直执行下去直到我们得到的数组长度都是1为止。这个图被称作递归树,它描述了递归操作是如何表现的,而且它看起来确实像是一棵树(在顶部,树叶在底部,在现实世界中它确实看起来像是一棵倒着的树)。

注意上图中的每一行,元素的总数都是n。为了看明白,你需要单独的查看每一行。第一行只包含了一个长度为n的数组上的mergeSort的调用,所以元素的总数就是n。第二行有两个长度为n/2的数组上的mergeSort的调用。但是n/2 + n/2 = n,所以这一行的元素总数也是n。第三行,我们有四次调用,每次都发生在长度为n/4的数组上,结果元素的总数相当于n/4 + n/4 + n/4 + n/4 = 4n/4 = n。依然是n个元素。同时注意图中的每一行的调用过程都会对所有被调用函数返回的结果执行一个merge操作。例如,图中用红色标明的圆圈需要对n/2个元素进行排序。为了达到目的,他需要把n/2长度的数组分成两个n/4长度的数组,然后递归的调用mergeSort来给那些数组排序(这些调用都用绿色来标明),然后把他们合并到一起。这个合并操作需要合并n/2个元素。在树中的每一行,被合并的元素的总数是n。在我们刚刚浏览的那一行,我们的函数合并了n/2个元素,并且右边的函数(用蓝色标明)也合并了它自己的n/2个元素。结果就是我们正在看的这一行需要被合并的元素有n个。

根据这一点我们可以知道,每一行的复杂度是$\Theta(n)$。我们知道图中的行的数目,也叫递归树的深度,将会是$log(n)$。这个推理跟我们分析二分搜索算法的复杂度时用到的完全一样。我们有$log(n)$行,并且每一行是$\Theta(n)$,因此mergeSort的复杂度是$\Theta(n * log(n))$。这比选择排序的$\Theta(n^2)$要好得多($log(n)$比$n$小得多,所以$nlog(n)$比$nn=n^2$小的多)。如果你觉得听起来有点复杂,别担心:第一次看的时候本来就没那么简单。在你用你最喜爱的编程语言实现了归并排序并验证它确实有用之后,重新访问这一部分并阅读相关的论点。

正如你在最后这个例子里看到的,复杂度分析允许我们比较不同的算法并确定哪一个更好。在这些情形下,我们现在可以确定,在处理大型数组的时候,归并排序胜过选择排序。如果没有我们发展的算法分析的理论背景,这个结论将会是很难描述的。在实际中,运行时为$\Theta(n * log(n))$的排序算法确实被用到了。例如,Linux内核使用的一个叫堆排序的算法,跟我们这里探索的归并排序拥有相同的运行时间,即$\Theta(n log(n))$,因此它也是最佳的。注意,我们并没有证明这些排序算法都是最优的。做这种工作需要涉及更多的数学相关的讨论点,但是请放心,从复杂度的角度来看它们都不可能再优化了。

读完这篇教程,你对于算法复杂度分析的感知能力应该能够帮你设计更快的程序,并且你会把优化工作放到真正重要的东西上而不是那些不重要的小细节上,你的工作也将会更有成效。补充一下,这篇文章中提到的数学语言和符号,比如大O符号,对于你跟其他软件工程师的沟通是很有帮助的,特别是当你们在讨论算法的运行时间的时候。因此,非常希望你们能够使用获取的新知识来进行讨论。

关于

这篇文章是在创意共享3.0署名协议下授权的。这意味着你可以对它进行复制/粘贴、分享、发表到你自己的网站、修改或者其他你需要做的操作,前提是你需要提到我的名字。如果你基于我的作品开展你的工作,尽管不是强制性的,我仍然鼓励你使用创意共享协议发表你自己的文章,这样可以方便其他人的分享和协作。同样的,我必须在这里标明我所用到的一些别人的作品。你在这个页面看到的俏皮的图标来自fugue icons。你在这里的设计中看到的漂亮的条纹样式是由Lea Verou创作的。以及,更重要的是,我知道的这些能够让我写出这篇文章的算法知识是由我的教授Nikos PapaspyrouDimitris Fotakis传授给我的。

我现在是雅典大学的密码学博士候选人。当我写这篇文章的时候,我还是雅典国立技术大学电气与计算机工程学院的一名本科生,主修软件工程,同时是希腊信息学竞赛的一名指导员。在工业领域,我是deviantART开发团队的一员,这是一个给艺术家使用的社交网站。我也是GoogleTwitter的安全团队的成员,同时还参与了两个创业公司,Zino和Kamibu,分别是社交网络和电子游戏开发。如果你喜欢这篇文章,可以关注我的TwitterGithub,如果需要联系我,可以给我发电子邮件。很多年轻的程序员还不太擅长英语。如果你想把这边文章翻译成你的母语从而让更多人可以阅读它,发邮件给我就行了。

感谢阅读。我并没有通过写这篇文章获得报酬,所以如果你喜欢它,发封邮件给我打个招呼吧。我很乐意收到来自世界各地的照片,所以请随意附上一张你和你所在城市的照片!

参考文献

  1. Cormen, Leiserson, Rivest, Stein. 算法导论, 麻省理工学院出版社.
  2. Dasgupta, Papadimitriou, Vazirani. 算法, 麦克劳·希尔出版集团.
  3. Fotakis. 雅典国立技术大学的 离散数学 课程.
  4. Fotakis. 雅典国立技术大学的 算法与复杂度 课程.
*****

本文由 Kholin 写于 2017年07月30日

知识共享许可协议 本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

*****