定义

所谓的时间复杂度，是一种用来对程序运行时间评估描述的函数。表示的方式一般都是大O()符号，在输入值不同，时间的变化范围也不同，所以可以称为渐近的。我们平常所使用的都是最坏情况复杂度，即输入取任意值得到的最大运行时间，记为T(n)。当然还有最好情况和平均情况，不过较少使用，也是在具体情况下用来评估。

如何计算时间复杂度

时间复杂度的计算方法统称来讲是大O推导法，从代码的执行次数上开始分析，比如如果一个代码的执行次数是常数量，并不随着我们的输入变化而变化，那么时间复杂度就是O(1)，反之，如果和输入n有关就需要进行分析，看下面代码例子：

1
2
3

for i := 0;i < n;i ++ {  // 1 
    fmt.Println("Hello Go!") // 2
}

这段代码就是执行了n+1次1行，执行了n次2行，所以是2n+1次，即T(n)=2n+1，时间复杂度就是O(n)。这里就有我们刚才提到的大O推导法，推导法的规则可以分为：

• 当n逐渐增大趋于无穷，常数量可以忽略不计，比如T(n)=n+1000，时间复杂度为O(n)。
• 大O的表示可以忽略系数，阶数与n对时间的变化影响更大，比如T(n)=2$n^2$+3，时间复杂度为O($n^2$)
• 忽略低阶，使用高阶作为时间复杂度，高阶的影响更大，比如T(n)=3$n^3$+2$n^2$+3,时间复杂度为O($n^3$)
• 在顺序执行或者条件判断等类似情况下，选择其中时间复杂度最大的作为整体的时间复杂度，比如下面的代码：

1
2
3
4
5
6
7
8

for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
        fmt.Println("时间复杂度为O(mn)")
    }
}
for i := 0; i < n; i++ {
    fmt.Println("时间复杂度为O(n)")
}

这里的时间复杂度就是O(mn)，条件判断的处理方式也同理，所以比较简单的时间复杂度的计算方式就是这样子，那么看一下下面这段代码的时间复杂度：

1
2
3
4

for i := 1;i < n;i ++ {
    i *= 2
    fmt.Println(i)
}

这段代码首先我们能看出来是和n有关系的，但是真的是执行了n次吗？因为i *= 2这个条件的在，让原先的执行次数缩小了很多，由$2^c$=n，推出c=$\log_2 n$，但是这里的2，可以是3、4…任何数，所以这个时间复杂度表示为O($\log n$)，再举一个经典递归，斐波那契数列的例子：

1
2
3
4
5
6
7

func example(n int) int {
    if n <= 1 {
        return 1
    } else {
        return example(n-1) + example(n-2)
    }
}

这是著名的斐波那契数列问题，也是经典的递归问题，这道题输入正整数，如果n是1的话，就执行一次，但是如果输入一个未知的n的话，执行的就是$2^0$+$2^1$+$2^2$+…+$2^n$，所以时间复杂度为O($2^n$)。

常见的时间复杂度

首先时间复杂度有一个优劣对比，即

O(1) < O($\log n$) < O(n) < O($n\log n$) < O($n^2$) < O($n^3$) < O($2^n$) < O($n!$) < O($n^n$)，

我们多数情况下在对比时间复杂度是排序算法和查找算法。下面是常见的几种算法的时间复杂度：

注：排序算法的稳定性指的是值相等的元素的前后顺序经过排序算法后是否会改变。

常见的时间复杂度处理的数据规模

如果你经常刷LeetCode，会看到题干和样例下面有提供一些数据规模，这里的数据规模其实就限制或者说告诉你可以用怎么样的时间复杂度进行计算，不然每次都用暴力解，很多题是会超时的，下面是几个常见的时间复杂度大致对应的数据规模：