写在前面

时间复杂度与空间复杂度直接决定着一个算法的好坏，而大多时候在设计算法是时间复杂度要优先于空间复杂度。

时间复杂度是什么(以下内容来着维基百科)

在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。

为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。

相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为 T(n) ，定义为任何大小的输入 n 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数 T(n) 的自然特性加以分类，举例来说，有着 T(n) = O(n) 的算法被称作“线性时间算法”；而 T(n) = O(M**n) 和 M**n= O(T(n)) ，其中 M ≥ n > 1 的算法被称作“指数时间算法”。

常见算法时间复杂度

搜索

image.png

排序

image.png

数据结构

image.png

堆

image.png

图

image.png

计算时间复杂度

算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述
1.在一个函数中，常数项对于函数的增长速度并不大，随意当T(n)=一个常数事，我们就可以说这个算法的时间复杂度为O(1)；

1
2
3
4
5
func main() {
   i := 1
   fmt.Println(i)
}
// 该函数总共两条执行语句，所以时间复杂度T(n) = 2，所以时间复杂度为O(1)

2.如果T(n)不等于一个常数项时，可直接将常数项省略

1
2
3
4
5
6
7
for i := 0; i < n; i++ {
	sum += i
}
sum += 1
sum += 2
sum += 3
此函数共执行了 n+3次，所以T(n) = n+3，时间复杂度为O(n)

3.对于有高次幂的，低次幂的影响可以说是微乎其微。比如n^3对于n^2,n^2对于n，由于时间复杂度要求不是特别高，所以低次幂直接忽略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for i := 0; i < n; i++ {

        for j := 0; j < n; j++ {

            for k := 0; k < n; k++ {
                // xxx
            }
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
                // xxx
        }
    }
上面函数的执行次数为n^3 + n^2，所以T(n) = n^3 + n^2, 时间复杂度为O(n^3)

4.因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。

1
2
比如
T(n) = 3n^3，此时时间复杂度为 O(n^3)。

综合一下:只取最高次幂，最高次幂常数归1