一、引言：时间复杂度的意义

时间复杂度的意义

究竟什么是时间复杂度呢？让我们来想象一个场景：某一天，小灰和大黄同时加入了一个公司......

一天过后，小灰和大黄各自交付了代码，两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒，内存占用5MB。小灰的代码运行一次要花100秒，内存占用500MB。于是......

由此可见，衡量代码的好坏，包括两个非常重要的指标：

1. 运行时间；
2. 占用空间。

二、基本操作执行次数：四个生活场景比喻

基本操作执行次数

关于代码的基本操作执行次数，我们用四个生活中的场景，来做一下比喻：

场景1：线性增长

场景1：给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？

答案自然是 3 × 10 = 30天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 3 × n = 3n 天。

如果用一个函数来表达这个相对时间，可以记作 T(n) = 3n。

场景2：对数增长

场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那么小灰把面包吃得只剩下1寸，需要多少天呢？

这个问题翻译一下，就是数字16不断地除以2，除几次以后的结果等于1？这里要涉及到数学当中的对数，以2为底，16的对数，可以简写为log₂16。

因此，把面包吃得只剩下1寸，需要 5 × log₂16 = 5 × 4 = 20 天。

如果面包的长度是 N 寸呢？

需要 5 × log₂n = 5log₂n天，记作 T(n) = 5log₂n。

场景3：常数时间

场景3：给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？

答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系。

如果面包的长度是 N 寸呢？

无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T(n) = 2。

场景4：平方增长

场景4：给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间.....每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？

答案是从1累加到10的总和，也就是55天。

如果面包的长度是 N 寸呢？

此时吃掉整个面包，需要 1+2+3+......+ n-1 + n = (1+n)×n/2 = 0.5n² + 0.5n。

记作 T(n) = 0.5n² + 0.5n。

三、从生活场景到代码实现

上面所讲的是吃东西所花费的相对时间，这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景，分别对应了程序中最常见的四种执行方式：

场景1：线性执行

场景1：T(n) = 3n，执行次数是线性的。

void eat1(int n) { for (int i = 0; i < n; i++) { System.out.println("等待一天"); System.out.println("等待一天"); System.out.println("吃一寸面包"); } }

场景2：对数执行

场景2：T(n) = 5log₂n，执行次数是对数的。

void eat2(int n) { for (int i = 1; i < n; i *= 2) { System.out.println("等待一天"); System.out.println("等待一天"); System.out.println("等待一天"); System.out.println("等待一天"); System.out.println("吃一半面包"); } }

场景3：常数执行

场景3：T(n) = 2，执行次数是常量的。

void eat3(int n) { System.out.println("等待一天"); System.out.println("吃一个鸡腿"); }

场景4：平方执行

场景4：T(n) = 0.5n² + 0.5n，执行次数是一个多项式。

void eat4(int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { System.out.println("等待一天"); } System.out.println("吃一寸面包"); } }

四、渐进时间复杂度（大O表示法）

渐进时间复杂度

有了基本操作执行次数的函数 T(n)，是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。

比如算法A的相对时间是T(n) = 100n，算法B的相对时间是T(n) = 5n²，这两个到底谁的运行时间更长一些？这就要看n的取值了。

所以，这时候有了渐进时间复杂度（asymptotic time complexity）的概念，官方的定义如下：

若存在函数 f(n)，使得当n趋近于无穷大时，T(n) / f(n)的极限值为不等于零的常数，则称 f(n) 是 T(n) 的同数量级函数。

记作 T(n) = O(f(n))，称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

大O表示法的推导原则

如何推导出时间复杂度呢？有如下几个原则：

1. 如果运行时间是常数量级，用常数1表示；
2. 只保留时间函数中的最高阶项；
3. 如果最高阶项存在，则省去最高阶项前面的系数。

四个场景的时间复杂度推导

让我们回头看看刚才的四个场景。

场景1：线性时间复杂度

场景1：

T(n) = 3n

最高阶项为3n，省去系数3，转化的时间复杂度为：

T(n) = O(n)

场景2：对数时间复杂度

场景2：

T(n) = 5log₂n

最高阶项为5log₂n，省去系数5，转化的时间复杂度为：

T(n) = O(log n)

场景3：常数时间复杂度

场景3：

T(n) = 2

只有常数量级，转化的时间复杂度为：

T(n) = O(1)

场景4：平方时间复杂度

场景4：

T(n) = 0.5n² + 0.5n

最高阶项为0.5n²，省去系数0.5，转化的时间复杂度为：

T(n) = O(n²)

时间复杂度比较

这四种时间复杂度究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：

O(1) < O(log n) < O(n) < O(n²)

在编程的世界中有着各种各样的算法，除了上述的四个场景，还有许多不同形式的时间复杂度，比如：

O(n log n), O(n³), O(m×n), O(2ⁿ), O(n!)

今后遨游在代码的海洋里，我们会陆续遇到上述时间复杂度的算法。

五、时间复杂度的巨大差异

时间复杂度的巨大差异

我们来举一个例子：

算法A的相对时间规模是T(n) = 100n，时间复杂度是O(n)

算法B的相对时间规模是T(n) = 5n²，时间复杂度是O(n²)

算法A运行在小灰家里的老旧电脑上，算法B运行在某台超级计算机上，运行速度是老旧电脑的100倍。

那么，随着输入规模 n 的增长，两种算法谁运行更快呢？

从表格中可以看出，当n的值很小的时候，算法A的运行用时要远大于算法B；当n的值达到1000左右，算法A和算法B的运行时间已经接近；当n的值越来越大，达到十万、百万时，算法A的优势开始显现，算法B则越来越慢，差距越来越明显。

这就是不同时间复杂度带来的差距。

六、常见算法的时间复杂度

理解了时间复杂度的基本概念和四种常见增长模式后，让我们看看这些模式在实际算法中的应用。以下是几种常见算法及其对应的时间复杂度：

1. 二分查找（Binary Search）

时间复杂度：O(log n)

对应增长模式：对数增长（场景2）

二分查找是一种在有序数组中查找特定元素的算法。每次比较都将搜索范围减半，因此时间复杂度为对数级。

int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }

2. 冒泡排序（Bubble Sort）

时间复杂度：O(n²)

对应增长模式：平方增长（场景4）

冒泡排序通过重复遍历列表，比较相邻元素并交换位置，将最大元素逐步"冒泡"到末尾。需要两层嵌套循环，时间复杂度为平方级。

void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }

3. 快速排序（Quick Sort）

平均时间复杂度：O(n log n)

对应增长模式：线性对数增长（文中提到的 O(n log n)）

快速排序采用分治策略，选择一个基准元素，将数组分为两部分，递归排序。平均情况下时间复杂度为 O(n log n)。

void quickSort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; }

4. 斐波那契数列递归（Fibonacci Recursive）

时间复杂度：O(2ⁿ)

对应增长模式：指数增长（文中提到的 O(2ⁿ)）

递归计算斐波那契数列会产生指数级的时间复杂度，因为存在大量重复计算。

int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); }

5. 数组访问（Array Access）

时间复杂度：O(1)

对应增长模式：常数时间（场景3）

通过索引直接访问数组元素，无论数组多大，访问时间都是常数。

int getElement(int[] arr, int index) { return arr[index]; // O(1) 操作 }

6. 线性搜索（Linear Search）

时间复杂度：O(n)

对应增长模式：线性增长（场景1）

遍历数组中的每个元素，直到找到目标或遍历完所有元素。

int linearSearch(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) return i; } return -1; }

通过以上示例可以看出，不同算法的时间复杂度对应着我们在前面讨论的不同增长模式。理解这些模式有助于我们在实际编程中选择合适的算法，优化程序性能。