算法基础—时间复杂度

大 O 表示法精髓：忽略低阶、常量、系数项。比如：$T(n)=O (2n^2 + 2n + 2) = O (n^2)$

1. 时间复杂度分析原则

1.1 只关注循环执行最多的代码

我们在分析一段代码的时间复杂度的时候，只关注循环次数最多的那一段代码就可以了。举例：

private static int calculate(int n) {
    int sum = 0;
    int i = 0;
    for (; i < n ; i ++ ) {
        sum += i;
    }
    return sum;
}

2、3行代码执行都是常量级，4、5行代码执行 n 次，所以总复杂度 O(n) 。

1.2 加法法则

加法法则其实和 1.1 比较相似，1.1 是关注的某一小块代码，加法法则关心的是一大段代码，其中包含了多个小块代码。举例：

private static int calculate(int n) {
    int sum = 0;

    int i = 0;
    for (; i < 100; i++) {
        sum += i;
    }

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

    int x = 0;
    int y = 0;
    for (; x < n; x++) {
        for (; y < n; y++) {
            sum += x * y;
        }
    }

    return sum;
}

第一小块代码时间复杂度为 O(1) ，第二小块为 O(n) ，第三小块为 O($n^2$) 。我们取最大量级，最终时间复杂度为 O($n^2$) 。总的时间复杂度就等于量级最大的那段代码的时间复杂度。

1.3 乘法法则

乘法法则适用于代码中出现嵌套循环，总的时间复杂度等于嵌套内外代码时间复杂度的乘积。

private static int calculate(int n) {
    int sum = 0;
    int j = 0;
    for (; j < n; j++) {
        sum += cal(j);
    }
    return sum;
}

private static int cal(int n) {
    int sum = 0;
    int j = 0;
    for (; j < n; j++) {
        sum += j;
    }
    return sum;
}

calculate()方法时间复杂度 O(n) ，cal()方法时间复杂度同样为 O(n) ，总的时间复杂度为 O($n^2$) 。

注意事项：无论是使用加法法则还是乘法法则，在计算时间复杂度的过程中，不可随意舍去系数项，计算完成得出结果之后才能按原则省略。（中学数学）

2. 常用复杂度量级及示例

按照时间复杂度依次递增，列出了常用时间复杂度量级：

常量阶O(1) 、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、次方阶O($n^2$)、O($n^3$)、O($n^k$)、指数阶O($2^n$)、阶乘阶O(n!)

我们可以粗略的认为，越高阶复杂度的算法，执行效率越低。

2.1 常量阶O(1)

1
2
3

int m = 1;
int n = 1;
int sum = m + n;

虽然有3行代码，但是时间复杂度是 O(1) 不是 O(3) 。即使再加 1000行代码，依旧是 O(1) 。

小结：只要代码中不存在循环、递归，无论是1行、10行还是1万行，时间复杂度都是 O(1) 。

补充：经过他人提醒，这里补充说明下，存在循环不意味着时间复杂度就是 O(n) 了，也可能是 O(1) 。

2.2 对数阶O($logn$)

对数阶其实不难，本质其实是中学数学。先看一段代码：

private static void logn(int n) {
    int i = 1;
    for (; i < n ; i ++) {
        i = i * 2;
    }
}

在代码的执行过程中，i 的取值如下：

$1、2、4、8、16……m……n$

我们换算一下就变成了：

$2^0、2^1、2^2、2^3、2^4……2^k……n$

当 $2^k$ 的值无限接近 n 时，即 $2^k=n$ 。此时，k 为执行次数， $k=log_2n$。时间复杂度为：O($log_2n$)。

如果将乘数从 2 改成 5 ，时间复杂度变为了 O($log_5n$)。而中学数学告诉我们： $log_5n = log_52 * log_2n$ 。

而系数是可以忽略的，所以我们在对数阶时间复杂度的表示方法里，忽略对数的“底”，统一表示为 O($logn$)。

注意事项

思考一个问题: O(1) 在实际工程应用中一定比 O(n) 快吗？

答案是不一定，比如在 O(1) 的算法中有 100 行代码，而在 O(n) 的算法中，传入的 n 值为一个很小的数，比如 2 。那么很明显，此时 O(1) 的算法反而执行更慢。

小结：算法是死的，实际业务是活的。在实际使用过程中，需要结合具体的场景来选择适合的算法。

3. 不确定的时间复杂度

上述示例代码的时间复杂度都是确定值，下面看一个不确定的。

private static int findByIndex(int[] array, int n, int x) {
    int i = 0;
    int result = -1;
    for (; i < n; ++i) {
        if (array[i] == x) {
            result = i;
            break;
        }
    }
    return result;
}

3.1 最好、最坏、平均复杂度

这段代码的含义是从一个长度为 n 数组中找出值为 x 的角标。这段代码的时间复杂度是 O(n) 吗？

如果第一个的值是 x ，时间复杂度为 O(1) ；如果最后一个的值是 x ，时间复杂度为 O(n) 。不考虑数组中没有值为 x 的情况。为了表示代码在不同情况下的不同时间复杂度，我们引入几个概念。

最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度。顾名思义，就不做解释了。

上述示例最好情况时间复杂度 O(1) ，最坏情况时间复杂度 O(n) ，平均情况时间复杂度计算如下，一共有 n 种情况，每一种情况对应的执行次数为 1、2、3……n 。所以平均复杂度从 1 到 n 的累加除以 n ，小学数学。

$\frac{1+2+3+4+...+n}{n}=\frac{1+n}{2}$

忽略常量、系数项，还是 o(n) 。

3.2 均摊时间复杂度

先看一个示例：

int[] array = new int[n];
int count = 0;

void insert(int val) {
    
    if (count == array.length) {
        int sum = 0;
        for (int i = 0; i < array.length; ++i) {
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
    }

    array[count] = val;
    ++count;
}

这段代码的意思大致是：往数组中不断添加元素，当 count 值等于数组长度时，遍历数组元素，将累加结果赋值给数组的第一个值。我们来思考一下这段代码的时间复杂度。

array.length = n ，当 count 从 0 到 n-1 时，都不会进入 if 语句，只会给 array 数组赋值，此时时间复杂度为 O(1) ；当 count = n 时，进入 if 语句，执行 for 循环语句，此时时间复杂度为 O(n) 。

很明显能发现，最好情况时间复杂度为 O(1) ，最坏情况时间复杂度 O(n) 。

下面计算平均时间复杂度，总共有 n+1 种情况，前 n 种（count 从 0 到 n-1）代码执行一次，最后一种执行 n 次。公式如下：

$\frac{1*n+n}{n+1}=\frac{2n}{n+1}$

很明显，最终的平均时间复杂度为 O(1) 。

通过这种数学方式计算平均时间复杂度没有问题，有没有更简单的方法呢？我们来思考下 insert 相较于findByIndex 有什么不同？

insert 方法在所有的可能性中只有一种为 O(n)，其他所有情况都是 O(1) 。
insert 方法有规律可循，每执行 n 次 O(1) 算法会接着执行一次 O(n) 算法。

针对这种特殊场景，我们引入 摊还分析法。通过该方法分析出来的时间复杂度称为均摊时间复杂度。还是刚刚的例子，每执行一次 O(n) 算法，之前都执行了 n 次 O(1) 算法，那我们把这次执行均摊到之前的 n 次上，时间复杂度不还是 O(1) 吗？思路大概就是这样子。

其实我个人认为均摊到前 n 次，用数学表示不还是除以 n 吗？感觉和平均时间复杂度算法没有什么本质的区别。以下引用王争在《数据结构与算法之美》中写道的：

尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度，但其实我个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法，摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。

参考资料：

王争的《数据结构与算法之美》