6.11 时间复杂度

“二哥，为什么要讲时间复杂度呀？”三妹问。

“因为接下来要用到啊。后面我们学习 ArrayList、LinkedList 的时候，会比较两者在增删改查时的执行效率，而时间复杂度是衡量执行效率的一个重要标准。”我说。

“到时候跑一下代码，统计一下前后的时间差不更准确吗？”三妹反问道。

“实际上，你说的是另外一种评估方法，这种评估方法可以得出非常准确的数值，但也有很大的局限性。”我不急不慢地说。

第一，测试结果会受到测试环境的影响。你比如说，同样的代码，在我这台 iMac 上跑出来的时间和在你那台华为的 MacBook 上跑出的时间可能就差别很大。

第二，测试结果会受到测试数据的影响。你比如说，一个排序后的数组和一个没有排序后的数组，调用了同一个查询方法，得出来的结果可能会差别特别大。

“因此，我们需要这种不依赖于具体测试环境和测试数据就能粗略地估算出执行效率的方法，时间复杂度就是其中的一种，还有一种是空间复杂度。”我继续补充道，“如果你后面刷 LeetCode的话，对时间复杂度这个概念也会比较依赖。”

来看下面这段代码：

public static int sum(int n) {
    int sum = 0; // 第 1 行
    for (int i=0;i<n;i++) { // 第 2 行
        sum = sum + 1; // 第 3 行
    } // 第 4 行
    return sum; // 第 5 行
}

这段代码非常简单，方法体里总共 5 行代码，包括“}”那一行。每段代码的执行时间可能都不大一样，但假设我们认为每行代码的执行时间是一样的，比如说 unit_time，那么这段代码总的执行时间为多少呢？

“这个我知道呀！”三妹喊道，“第 1、5 行需要 2 个 unit_time，第 2、3 行需要 2nunit_time，总的时间就是 2(n+1)*unit_time。”

“对，一段代码的执行时间 T(n) 和总的执行次数成正比，也就是说，代码执行的次数越多，花费的时间就越多。”我总结道，“这个规律可以用一个公式来表达：”

T(n) = O(f(n))

f(n) 表示代码总的执行次数，大写 O 表示代码的执行时间 T(n) 和 f(n) 成正比。

这也就是大 O 表示法，它不关心代码具体的执行时间是多少，它关心的是代码执行时间的变化趋势，这也就是时间复杂度这个概念的由来。

对于上面那段代码 sum() 来说，影响时间复杂度的主要是第 2 行代码，其余的，像系数 2、常数 2 都是可以忽略不计的，我们只关心影响最大的那个，所以时间复杂度就表示为 O(n)。

常见的时间复杂度有这么 3 个：

1）O(1)

代码的执行时间，和数据规模 n 没有多大关系。

括号中的 1 可以是 3，可以是 5，可以 100，我们习惯用 1 来表示，表示这段代码的执行时间是一个常数级别。比如说下面这段代码：

int i = 0;
int j = 0;
int k = i + j;

实际上执行了 3 次，但我们也认为这段代码的时间复杂度为 O(1)。

再举一个简单的例子。当我们访问数组中的一个元素时，它的时间复杂度就是常数时间复杂度 O(1)。

int[] nums = {1, 2, 3, 4, 5};
int x = nums[2]; // 访问数组中下标为2的元素，时间复杂度为 O(1)

2）O(n)

时间复杂度和数据规模 n 是线性关系。换句话说，数据规模增大 K 倍，代码执行的时间就大致增加 K 倍。

当我们遍历一个数组时，它的时间复杂度就是线性时间复杂度 O(n)。

int[] nums = {1, 2, 3, 4, 5};
for (int i = 0; i < nums.length; i++) { // 遍历整个数组，时间复杂度为 O(n)
    System.out.println(nums[i]);
}

3）O(logn)

时间复杂度和数据规模 n 是对数关系。换句话说，数据规模大幅增加时，代码执行的时间只有少量增加。

来看一下代码示例，

public static void logn(int n) { 
    int i = 1;
    while (i < n) {
        i *= 2;
    }
}

换句话说，当数据量 n 从 2 增加到 2^64 时，代码执行的时间只增加了 64 倍。

遍历次数 |   i
----------+-------
    0     |   i
    1     |  i*2
    2     |  i*4
   ...    |  ...
   ...    |  ...
    k     |  i*2^k 

再举个例子。当我们对一个已排序的数组进行二分查找时，它的时间复杂度就是对数时间复杂度 O(log n)。

int[] nums = {1, 2, 3, 4, 5};
int target = 3;
int left = 0, right = nums.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        System.out.println("找到了，下标为" + mid);
        break;
    } else if (nums[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

4）平方时间复杂度 O(n^2)

当我们对一个数组进行嵌套循环时，它的时间复杂度就是平方时间复杂度 O(n^2)。

int[] nums = {1, 2, 3, 4, 5};
for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < nums.length; j++) {
        System.out.println(nums[i] + " " + nums[j]);
    }
}

5）指数时间复杂度 O(2^n)

当我们递归求解一个问题时，每一次递归都会分成两个子问题，这种情况下，它的时间复杂度就是指数时间复杂度 O(2^n)。

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

上面的代码是递归求解斐波那契数列的方法，它的时间复杂度是指数级别的。

“好了，三妹，这节就讲到这吧，理解了上面 5 个时间复杂度，后面我们学习 ArrayList、LinkedList 的时候，两者在增删改查时的执行效率就很容易对比清楚了。”我伸了个懒腰后对三妹说。

“好的，二哥。”三妹重新回答沙发上，一盘王者荣耀即将开始。

---

GitHub 上标星 10000+ 的开源知识库《二哥的 Java 进阶之路》第一版 PDF 终于来了！包括Java基础语法、数组&字符串、OOP、集合框架、Java IO、异常处理、Java 新特性、网络编程、NIO、并发编程、JVM等等，共计 32 万余字，500+张手绘图，可以说是通俗易懂、风趣幽默……详情戳：太赞了，GitHub 上标星 10000+ 的 Java 教程

微信搜 沉默王二 或扫描下方二维码关注二哥的原创公众号沉默王二，回复 222 即可免费领取。