不复杂的时间复杂度

首先，为什么会有「时间复杂度」和「空间复杂度」这两个概念呢？
人在做任何事情时，都希望投入最少时间、金钱或精力等就能获得最佳收益。而在针对问题设计算法时，人们同样也希望花费最少时间，占用最少存储空间来解决问题。因此，就有了「时间复杂度」和「空间复杂度」两项指标来分别衡量算法在时间维度上的效率和空间维度上的效率。算法解决问题用时越短，时间维度上的效率越高；占用存储空间越少，空间维度上的效率就越高。

在这一讲中，我们将先讨论「时间复杂度」这一概念。

大O表示法

小白同学：衡量在时间维度的效率的话很简单呀，直接把算法写出来跑一遍，计时一下运行了多少时间就好了！

但仔细一想，很快就能发现这种“马后炮”方法的不足：运行的机器硬件，实现的编程语言以及操作系统等等因素都会影响运行的时间，而我们希望的是衡量算法时间效率的指标仅仅只由算法本身和数据规模大小来决定。所以这种“马后炮”方法并不能用来衡量算法在时间效率上的优劣。

那有没有什么办法能让我们用“肉眼”就能看出一段代码的执行时间呢？

先看下面这一段代码。

int cal(int n) {
   int sum = 0;
   int i = 1;
   for (; i <= n; i++) {
       sum = sum + i;
   }
   return sum;
}

我们用\(T(n)\)代表代码的执行时间，并假设每条语句的执行时间均为\(unitTime\)，以上语句的总执行次数为\(1+1+2 \times n+1\)，即\(2n + 3\)次，那么\(T(n) = unitTime \times (2n+3)\)。若用大O表示成正比的关系，那么该表达式就可以记为\(T(n) = O(2n + 3)\)。再把大O括号内的式子用\(f(n)\)表示，那么就是\(T(n) = O(f(n))\)。该式子表示这段代码的总执行时间\(T(n)\)与式子\(f(n)\)成正比，这就是大O时间复杂度表示法。

我们可以看到上面的计算都只是粗略的估计，所以大O表示法也只是用于表示代码执行时间随数据规模增长的变化趋势，所以它也叫做「渐进时间复杂度」，简称时间复杂度。这里的“渐进”就是指数据越来越大，趋近于极限的意思。

既然表示的只是变化趋势，那么很多细枝末节的东西就可以被忽略，所以我们只需要抓住\(f(n)\)中影响力最大的因子即可（通常为最高次项）。显然上述代码中影响力最大的因子是\(n\)（系数可以忽略），那么刚才的式子我们就可以直接记为\(T(n) = O(n)\)，表示代码的执行时间和数据规模大小成正比。

刚才我们是通过数出所有代码的总执行次数，再将最高次项去掉系数得出大O时间复杂度。那既然不需要再去计算那种细枝末节的东西，有没有更简单直接的方式来得出一段代码的时间复杂度呢？
答：有的，直接关注代码中循环执行次数最多的那段代码即可。

例如，在刚才的例子中，第4行代码和第5行代码显然就是循环执行次数最多的那段代码，那么\(T(n) = O(2n)\)，去掉系数，即可快速得出\(T(n) = O(n)\)。

几种常见的时间复杂度量级

在上一小节中，我们见到了量级为线性阶（linear）的时间复杂度。常见的时间复杂度量级还包括常数阶（constant），对数阶（logarithmic），平方阶（quadratic），立方阶（cubic），指数阶（exponential），阶乘阶（factorial）。

常数阶\(O(1)\)

int a = 1;
int b = 2;
int c = 3;

小白同学：总共3行代码，那时间复杂度不是\(O(3)\)吗，怎么会是\(O(1)\)呢？
答：\(O(1)\)是用来表示代码的执行时间为常数，即代码的执行时间并不随着n的增大而增长。这类的代码即便有10000行代码，时间复杂度也仍为\(O(1)\)。

对数阶\(O(logn)\)、线性对数阶\(O(nlogn)\)

while (n > 1)
    n = n/2

这段代码不断将 \(n\) 自除以2来接近1，假设该语句的执行次数为\(x\)，则\(\frac{n}{2^x} = 1\)，变换公式可得\(x = log_2n\)。所以这段代码的时间复杂度为\(O(log_2n)\)。

再看下面代码，同理，得出其时间复杂度为\(O(log_3n)\)。

while (n > 1)
    n = n/3

可实际上，不论是以 2 为底、以 3 为底，还是以 10 为底，所有对数阶的时间复杂度都是记为\(O(logn)\)。为什么呢？
答：因为对数之间是可以相互转换的。因为\(log_32 \times log_2n = log_3n\)，所以\(O(log_3n) = O(log_32 \times log_2n)\)。而\(log_32\)是个常数，我们在前面也提到过常量系数在大O表示法中是可以被忽略的，所以\(O(log_2n) = O(log_3n)\)。所以在量级为对数阶的复杂度里，我们干脆忽略对数的底，统一表示为\(O(logn)\)。

再看这段代码。

for (int i = 0; i < n; i++) {
  while (n > 1)
    n = n/2
}

将时间复杂度为\(O(logn)\)的代码执行n遍，即为\(O(nlogn)\)。

平方阶\(O(n^2)\)、立方阶\(O(n^3)\)

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

循环执行次数最多的代码为a++，执行次数为\(n^2\)，所以\(T(n) = O(n^2)\)。

立方阶同理，只要再多套一层for循环即可。

指数阶\(O(2^n)\)

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

阶乘阶\(O(n!)\)

int factorial(int n) {
    for (int i = 0; i < n; i++) {
				factorial(n - 1);
    }
}

循环执行次数最多的语句为factorial(n - 1)，在当前 \(n\) 下，会调用n次factorial(n - 1)，而在每个 \(n - 1\) 下，又会调用n - 1次factorial(n - 2)，以此类推，得执行次数为 \(n \times (n - 1) \times (n - 2) \times ... \times 1\)，即 \(n!\)。

时间效率排名

很明显，对于相同的数据规模，不同的时间复杂度在时间维度的表现上有着巨大的差异。

时间效率排名为（越靠右越代表算法的时间效率越低）：\(O(1) < O(logn) < O(n) < O(n^2) < O(n^3) < O(2^n)\)。

最好、最坏以及平均时间复杂度

此外，我们还需要知道，同一段代码在不同情况下会有不一样的时间复杂度，让我们看下面这段代码。

// Tell whether the array a contains x.
boolean contains(int[] a, x) {
    for (int i = 0; i < a.length; i++) {
        if (x == a[i])
            return true;
    }
    return false
}

首先，执行次数最多的语句很明显为if (x == a[i])。
接着问题来了，假如我们想找的元素x正好就处于数组的第一个位置，那么无论数组规模多大，该语句的执行次数都为\(1\)，此时\(T(n) = O(1)\)，这种情况就是最好时间复杂度（best-case time complexity）；假如我们想找的元素x不在数组中，那么这整个数组都会被遍历一遍，if (x == a[i])的执行次数为\(n\)，则\(T(n) =O(n)\) ，这种情况就是最坏时间复杂度（worst-case time complexity），我们通常会以最坏的角度来进行时间复杂度的评估。\(\frac{x+y}{y+z}\)

设 \(T_1(n)\), 设\(T_2(n)\), ...分别为所有可能情况下的时间复杂度；设 \(P_1(n)\), \(P_2(n)\), ...为这些对应情况的分布概率。则平均时间复杂度（average-case time complexity）为 \(P_1(n)T_1(n) + P_2(n)T_2(n)+ ...\)

平均时间复杂度通常来说较难计算，因为难以得出各类情况的分布概率，有时为了简便，会将最好时间复杂度以及最坏时间复杂度相加除以二来得出平均时间复杂度，例如上述代码的平均时间复杂度可以简单计算为\(O(\frac{1 + n}{2})\)，即为\(O(n)\)。

\(\Omega\) 表示法

除了大O表示法，你可能还会见过\(\Omega\)表示法和\(\Theta\)表示法。这三类表示法都可以用于表示时间复杂度，但是略有不同。大O表示法\(O(f(n))\)表示的是渐进上界（upper bound），即当数据规模越来越大时，算法的执行时间最多也不会超过\(M \cdot f(n)\)（M为某一常数）。接下来我们将详细介绍另外两种表示法。

\(\Omega\)表示法\(\Omega(f(n))\)表示的是渐进下界（lower bound），即当数据规模越来越大时，算法的执行时间最少也不会小于\(k \cdot f(n)\)（k为某一常数）。

那么如何快速地找出一段代码的渐进下界呢？

先看个例子，\(T(n)\)仍用于代表代码的总执行时间，并假设每条语句的执行时间均为\(unitTime\)。

假设某算法的总执行时间\(T(n) = unitTime \times (2^n + 5)\)，因为无论\(n\)有多大，\(unitTime \times (2^n + 5) \geq unitTime \times 2^n\)的式子恒成立，那么\(unitTime \times 2^n\)就可被称为是该算法在时间维度上的渐进下界，记为\(T(n) = \Omega(2^n)\)（\(unitTime\)为常量系数，可被忽略），表示该算法的执行时间最少不会小于\(k \cdot 2^n\)（\(k\)为某常数）。

所以要想用\(\Omega\)表示法表示代码的时间复杂度时，总结起来就是先列出\(T(n)\)，\(T(n) = unitTime \times 代码的总执行次数\)，再纠出\(T(n)\)中的最高次项，将其去掉系数即可，即\(T(n) = \Omega（去掉系数的最高次项）\)。这样就成功表示了这段代码在时间维度上的渐进下界了。

\(\Theta\)表示法

\(\Theta\)表示法\(\Theta(f(n))\)表示的是渐进紧确界（tight bound），即当数据规模越来越大时，算法的执行时间将落在\(k_1 \cdot f(n)\)和\(k_2 \cdot f(n)\)之间（\(k_1,k_2\)均为常数）。

那么如何用\(\Theta\)表示法表示算法的时间复杂度呢？

如果可以用同一个多项式表示一个算法的O和\(\Omega\)，那么这个多项式就是我们要求的渐进紧确界了。

例如：假设某算法的\(T(n) = unitTime \times （3n^3 + 2n + 7）\)。那么用大O表示其时间复杂度即为\(O(n^3)\)，用\(\Omega\)表示其时间复杂度即为\(\Omega(n^3)\)。两种表示法的多项式均为\(n^3\)，那么用\(\Theta\)表示该算法的时间复杂度即为\(\Theta(n^3)\)，表示该算法的执行时间落在\(k_1 \cdot n^3\)和\(k_2 \cdot n^3\)之间（\(k_1,k_2\)均为常数）。

Q & A

小白同学：「时间复杂度」这个概念和\(O、\Omega、\Theta\)这三种表示法的关系我还是有点搞不清哎？
答：首先，「时间复杂度」这个概念是用来衡量算法在时间维度上的增长趋势。这个概念具体可以用\(O、\Omega、\Theta\)这三种表示法表示。若想表示「渐进上界」就用O；想表示「渐进下界」就用\(\Omega\)；想表示「渐进紧确界」就用\(\Theta\)。实际工作中，最常用的是大O表示法。

 
小白同学：怎么感觉三种表示法的求法都一样？得出来的都是同样的多项式？
答：确实一样，基本求法都是最高次项去掉系数。尽管得出来的多项式相同，但是表达的意义却不尽相同：O表示算法的执行时间最多不超过\(k_1 \cdot f(n)\)；\(\Omega\)表示算法的执行时间最少不小于\(k_2 \cdot f(n)\)；\(\Theta\)表示算法的执行时间在\(k_3 \cdot f(n)\)和\(k_4 \cdot f(n)\)之间。（\(k_1,k_2,k_3,k_4\)均为常数）

 
小白同学：最开始的时候介绍了最好情况最坏情况，怎么后面又来了个渐进上界渐进下界？这两者是一样的吗，渐进上界（upper bound）就指的是最坏情况（worst-case），渐进下界（lower bound）就指的是最好情况（best-case），对吗？
答：错误。上界、下界和最坏、最好情况并不是一回事。让我们先看下面这个故事（摘选自Khan Academy）。

假设小白同学某天被抓进监狱，狱长告诉他只有玩完下面这个游戏才能放他走。

他给小明同学展示了两个一模一样的盒子，并告诉他游戏规则如下：

• A盒子有10到20只小虫子。
• B盒子有30到40只小虫子。
• 两个盒子在外观上一模一样，所以小明分不清哪个是A盒子，哪个是B盒子。
• 小明必须选出一个盒子，并吃掉里面所有的虫子。

具体地，A盒子里有17只小虫子，B盒子里有32只小虫子，不过小明并不知道。

接下里轮到小明做出选择了，前提假设小明喜欢少吃点虫子。

那么对于小明来说，很显然，最好的情况（best-case）就是选到A盒子。

那在这种场景下，吃到的虫子最少为10只（下界），最多为20只（上界）。

最坏的情况（worst-case）是选到B盒子。

那在这种场景下，吃到的虫子最少为30只（下界），最多为40只（上界）。

所以我们可以看出，无论是最好情况还是最坏情况，两种情况下都是存在上界和下界的。

同样也很容易看出，最坏情况里的上界是最最最糟糕的，而最好情况里的下界是最最最好的。

总结

本讲介绍了「时间复杂度」这一概念，用它来表示算法在时间维度上的效率。它不是计算算法具体耗时的，而是反映算法在时间维度上的一个趋势。时间复杂度具体可以用\(O、\Omega、\Theta\)这三种表示法表示，分别表示算法执行时间的「渐进上界」、「渐进下界」和「渐进紧确界」。此外还介绍了算法在最好、最坏、平均情况下的时间复杂度以及一些常见的时间复杂度量级。

参考

1. https://www.sohu.com/a/271774788_115128
2. https://mp.weixin.qq.com/s/rMfBC5PA8zIu9bPBYS8zBQ
3. https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation
4. https://blog.csdn.net/qq_41856733/article/details/89034055

创作不易，点个赞再走叭～