想理解算法时间复杂度的表示法,先要搞明白何谓“算法时间复杂度”。 如果你学过开车的话(没有的话,回忆一下初中物理),就会知道,挂一档时,可能发动机转十几圈,车轮才转一圈;但挂5档时,可能发动机转一圈,车轮就转了一圈。 换句话说,在不同挡位,发动机转一圈,车轮转多少是不一样的。 这个玩意儿背后,其实就是初中学过的轮轴原理。 设发动机旋转圈数为N,则不同挡位时,车轮旋转圈数M就等于N*X;若X比较大,那么这个挡位的行车速度就更快;否则行车速度更慢,但车轮驱动力更大,可以爬陡坡。 计算机解题也有类似的关系:当我们有N个数据时,需要多少个动作才能把它处理完呢? 如果是在N个数据中找最大的那个,那么我们至少要检查所有N个数据才可能找到最大值,对吧? 所以,对这个场景,我们的比较动作次数就等于N——换句话说,动作数和数据量是1:1的关系。 类似的,给N个数据排序,每个数据查一遍能完成排序吗? 除非它们本来就是排好序的,不然一遍肯定搞不完,对吧。 那么,需要搞多少遍呢? 最简单的,我们用冒泡法,每次都从头撸到尾,撸N次肯定够了。 撸N次,每次都要遍历所有N个数据,所以最终我们需要检查N^2次,对吧? 换句话说,未优化的冒泡法排序,比较次数和数据量是N^2:N的关系——用函数表示就是f(N^2)。 显然,就好像汽车发动机转动圈数和车轮转动圈数一样,计算机解题需要的大致步骤数和数据量也存在一个映射关系。 但和发动机/车轮之间只存在线性比例关系不同,计算机解题需要的步骤数和数据量可能存在线性关系,也可能存在指数关系或者对数关系。 仍然和我们关心发动机/车轮转速、因为它影响了我们的行车速度/爬坡加速能力一样,我们非常非常关心计算机解题所需步骤数和数据量之间的映射关系——因为这个映射关系反映了“解题会不会非常费力”这个事实。 和汽车挡位一样,我们希望能够粗略的把“算法解题的费力程度”分为几档——为什么不搞细致一些呢? 因为搞不细致。 CPU不同,计算机软硬件设计不同,都会影响执行每轮操作所需的时间。再加上cache、数据本身等等带来的随机影响……这就是本永远说不清的糊涂账。 所以,不妨忽略细节,只关注“算法规模和数据量N之间的大致映射关系”好了。 怎么“大致”呢? 当把“算法规模和数据量N之间的映射关系”写成一个多项式时,我们只关注它的最高次项就好了——反正是本糊涂账,没必要关注那些次要因素。 (实际上是连最高次项的系数都要忽略掉的!) 就好像不同品牌不同车型的汽车虽然都有1、2、3、4档,但它们相同挡位的扭矩/变速比/最高车速也不尽相同一样:大概知道是几档就行了,没必要精确到小数点后6位! (实际上可能连个位数甚至十位数都给忽略了!) 这玩意儿就是所谓的“大O标记法”。 很明显,大O标记法并不是什么“上界”。 它只是一个粗略的、关于算法消耗时间/空间和数据量N之间的函数关系的“挡位”罢了。 举例来说,当我们需要从N个数字中选出top 100时,我们可以遍历它100次,也可以想办法只遍历一次(比如搞个容量100的有序队列)——但这两个算法的复杂度都是O(N)。 没错,虽然“遍历100次”实际上执行的循环次数是100N,而有序队列版本只执行了N次,但它们的算法复杂度都是一样的! ——遍历100次版本可以争辩说,虽然我遍历的次数多,但我的处理逻辑简单!队列版看似只循环了一次,但它每次维护那个队列,执行的可远远不止100行代码! ——队列版则反驳说,我可以利用定制硬件提供的功能,所以其实我只执行了10行代码! ——100版反唇相讥:呵呵,每次访问定制硬件你都要清空指令缓存、切换总线模式,花费70倍的代价才能执行一条指令。还不赶紧砸钱优化你的硬件,不然还不如执行500条指令呢。 你看,算法研究者不可能越过纷繁复杂的现实,通过静态分析评判两个同档次算法的好坏——哪怕它们一个看似“愚蠢”的循环了100次、或者“愚蠢”的在每次循环中都执行一次复杂的队列维护操作。 当然,很明显,当我们需要top 10000时,循环10000次几乎可以肯定是蠢的;但如果只需要top 2,那么“队列版”简直蠢的无可救药。 但,这种细节问题应该丢给开发工程师在实践时通过profile优化——把它拿来浪费算法工程师的时间是一种犯罪。 因此,大O标记法明智的抛弃了所有低次项、以及最高次项的系数,仅仅回答了“这个算法的复杂度和问题规模N之间,大致是哪个档次的关系”。 理解了这个之后,问题就很容易回答了: O(n2):算法复杂度和问题规模是平方关系。换句话说,算法复杂度随着问题规模以平方关系迅速增长。 O(n):算法复杂度和问题规模是线性关系。换句话说,数据量大K倍,消耗时间/空间就大致增加K倍。 O(1):算法复杂度和问题规模无关。换句话说,哪怕你拿出几个PB的数据,我也能一步到位找到答案。 O(nlogn):算法复杂度和问题规模比线性更大,但比平方更小。 O(logN):算法复杂度和问题规模是对数关系。换句话说,数据量大幅增加时,消耗时间/空间只有少量增加(比如,当数据量从2增加到2^64时,消耗时间/空间只增加64倍) 对比一下: 一档:变速比极高,车速极慢,驱动力极大,用于起步。 二档:变速比较高,车速较慢,驱动力较大,用于起步过度到正常行驶。 三档:变速比一般,车速普通,驱动力一般,用于较复杂环境下正常行驶。 四档:变速比较低,车速稍快,驱动力较低,中速行驶用。 五档:变速比低,车速快,驱动力很低,用于较好路况或高速公路环境下高速行驶。 没错,大O标记法就是这样的存在。 重复一遍,它既不是上界,也不是下界。它就是一个粗略的、用于区分“算法复杂度和问题规模间映射关系”所在的“档次区间”的东西。 那么,所谓的“上界”又是怎么来的呢? 答案是:大O标记法是Knuth从数学中借来的一个符号;而这个符号在数学中另有其义。 在数学中,它的含义含有“上界”的意思——于是乎,O(1)写成O(N^2)并不是错的。 你看,“数学家”这么一出来当“杠精”,就给搞乱套了——人家非要说,按照数学规则,跑高速挂一档和挂五档都一样,你能咋地?! 反正这个符号你是从数学里“借”来的。现在正主来了:我不管你的上下文,也不管你有没有重新定义,反正它就是这个意思! Knuth有苦难言啊。我本来想拿这个粗略划分档次呢,结果你们故意和我捣蛋?行行行,我的想法不重要,数学最大。 于是他自己设计了个符号——Θ。 ——现在你们数学家就没话说了,用了Θ你就得照我的“档次论”来! 至于咱工程师嘛……别跟着那些蔫坏蔫坏的数学家学,更不要被这些人弄的晕头转向找不到北:在咱的大本营里,O就是档次!