算法时间复杂度分析

干货小结(TL;DR)

  1. 算法的运行时间不仅受到数据规模n的影响,还受到数据具体情况的影响(例如文中插入排序的例子)。

  2. 考虑一个算法的渐近时间复杂度的时候,一定要注意区分三种情况:最坏情况(用Big O notation)、最好情况(用Omega notation)、一般情况(用Theta notation)。

  3. 快速排序(quick sort)的最坏情况渐近时间复杂度为O(n^2),最好情况渐近时间复杂度为Ω(nlogn),一般情况渐近时间复杂度为Θ(nlogn),这里是参考网站


关于算法运行的最坏情况(worst case)、最好情况(best case)、一般情况(average case)

首先,我们需要考虑的问题是如何大致估计一个算法的运行时间。
答案是,假设各种类型的操作单元(例如加、减、乘、除、赋值等等操作)运行时间都相同,然后只需要统计完整运行算法时执行的操作次数f(n),就可以进行算法运行时间的估计。这里的n是数据规模。
当然,运行一个算法的操作次数f(n)除了受到数据规模n的影响以外,还会受到数据本身具体情况的影响。

例如,对一个存放有1到n的长度为n的数组进行从小到大的插入排序
在最坏情况下,数据是n到1倒着排的,那么插入排序算法需要1+2+…+n=n*(n+1)/2次操作才能完成,f(n)=n(n+1)/2;
在最好情况下,数据本身就是1到n从小到大排好的,那么插入排序算法只需要n次操作就可以完成,f(n)=n;
在一般情况下,数组中的1到n随机摆放,插入排序算法的操作次数f(n)介于n次和n*(n+1)/2次之间,当然,如果要具体计算的话,需要求出在1到n的所有可能的排列情况下操作次数的期望值。

所以,对于一个具体的算法来说,一定要注意算法操作次数f(n)有worst case、best case、average case三种情况。


渐近时间复杂度(asymptotic time complexity)是什么

很显然,对于不同类型的函数f(n)(例如n的指数函数或者n的多项式函数),随着n的增长,f(n)增长速度也不同。
因此,为了方便描述和比较不同类型的算法在数据规模n非常大的情况下,随着n的变化,运行时间如何变化,考虑算法的渐近时间复杂度(asymptotic time complexity)

最常用的三种渐近时间复杂度表示方法是大O(Big O notation)、Ω(Omega notation)、Θ(Theta notation),分别用来对算法在最坏情况、最好情况和一般情况下的操作次数作出渐近分类。

简单地理解,渐近时间复杂度就是对数据规模为n时,算法运行的操作次数f(n)的函数类型做出了区分。
例如,当算法在最坏情况下执行的操作次数f(n)是指数函数时,算法最坏情况下渐进时间复杂度用O(2^n)表示;
当算法在最坏情况下执行的操作次数f(n)是二次函数时,算法最坏情况下渐近时间复杂度用O(n^2)表示。


渐进时间复杂度中为什么忽略系数以及对数logn中的底数?

这是因为,按照我目前的理解,渐近时间复杂度的目的只是为了区分不同算法在数据规模n非常大的情况下,随着n的变化,运行时间如何变化,因此,只需要知道“指数函数比多项式函数增长快”、“对数函数比一次函数增长速度慢”等等这样的概念就足够了,而进行上述比较时,系数以及底数是无关紧要的。

这样,我们面对最坏情况渐近时间复杂度为O(2^n)的算法A和最坏情况渐近时间复杂度为O(n^2)的算法B时,就可以给出论断:
在数据量很大的时候,最坏情况下,算法A大概率比算法B需要更多的操作,因此也会大概率更慢(这里之所以强调大概率,是因为渐近时间复杂度忽略了系数等等,严格来说,在数据量不够大的时候直接用来做比较很可能没有意义,例如1000000n和2^n这两个函数,虽然前者比后者增长慢,但是在n=10的时候显然是1000000n更大)。

而至于诸如“算法A的操作次数f1(n)=2n,算法B的操作次数f2(n)=3n,所以算法A比算法B更好”这样的“绝对比较”,并不是渐近时间复杂度所需要考虑的范畴。

题外话

这篇文章是校本部图书馆清明假期闭馆期间,在图书馆旁边的Joy Cafe(中文名好像叫悦生活咖啡)咖啡店喝着美式咖啡写下的。店员小姐姐认真招待客人的样子真好看,声音也很好听,店里的BGM也很不错。

在店里听到的两首好听的BGM是:《是非题》、《遇见你的时候所有星星都落到我头上》。下次你喝着咖啡学算法的时候,不妨放来听听。