时间复杂度

阅读量 loading

一、什么是时间复杂度

我们经常会在算法时间复杂度分析中听到说某个算法的时间复杂度是 O(1) 、 O(n) 、 O(logn) 、 O(nlogn) 、 O(n^2) ，那么这里面的 O 和 n 到底是什么含义呢？

简单的来说：

• O ：描述的是算法的运行时间和输入数据之间的关系

注意这里是简单的来说，严格上的定义并不是这样子，但是可以这样子理解。但其实还不理解对吧，我们看下面这个代码：

    public static int sum(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

非常简单的一个数组求和运算。那么这个算法的时间复杂度是 O(n) ，怎么理解呢？其实在这个算法中， n 就是指 nums 中的元素个数， O(n) 就表示这个算法的时间复杂度是和 nums 中元素的个数成线性关系的，也就是说 nums 中元素的个数越多，时间复杂度越大。

那么这个 O 又是什么含义呢？其实 O 代表了忽略常数。因为我们知道一个时间复杂度的线性表达式的实际是这样子的： T = c1 * n + c2 ，对于上面这个求和的算法，对于数组中的每一个数字我们都做了什么操作呢？从数组中取出数字、把 sum 取值、对 sum 和当前数字求和、将求和结果重新存入 sum，这4个操作所花费的总时间就是线性表达式中的 c1。在求和过程中，初始化 sum 的值和最后将 sum 的值返回出去，那么这些操作的过程花费的时间就是表达式中的 c2。由于在实际的各个算法中，这个 c1 和 c2 的实际情况并不能统一的来量化出来，所以在实际计算时间复杂度的时候是要忽略掉这些常数。

二、举例说明

来看下下面3个时间复杂度表达式：

1. T = 2 * n + 2，时间复杂度是 O(n)
2. T = 2000 * n + 10000，时间复杂度是 O(n)
3. T = 1 * n * n + 0，时间复杂度是 O(n^2)

从算法时间复杂度来看，第3个的时间复杂度由于是 O(n^2) ，所以它要比第1个和第2个性能要差。但是这样子看，假如 n 等于10的话，算下来第2个表达式的时间复杂度是30000，而第3个时间复杂度才是100，明显第3个时间复杂度要小些，也就是性能要高一些。其实这也可以看出来：并不是说对于任意的输入 O(n^2) 的时间复杂度要比 O(n) 的时间复杂度要大。

其实这个 O 代表的是 渐进时间复杂度 ，它描述的是当 n 趋近于无穷大的情况下的时间复杂度。那么从这个层面来看，当 n 越大，上面第3个表达式的时间复杂度就要比第2个要越大。