1. 前言

在深入学习前，这些知识点要先知道，下面就让我们学习起来。

2. 参考资料

维基百科-时间复杂度

维基百科-空间复杂度

3. 时间频度

时间频度是一个算法中的语句执行的次数。记为 T(n)。

当T(n)在一些场景下可以：忽略常数项、忽略低次项、忽略系数

忽略常数项

如：T(n)=3n+2，当n趋向无穷大时，可以忽略常数项2；

忽略低次项

如：T(n)=3n+5n^8，当n趋向无穷大时，可以忽略低次项及其系数3n；

忽略系数

如：T(n)=3n^6，当n趋向无穷大时，可以忽略系数3。

4. 时间复杂度

算法的时间复杂度（Time complexity）是一个函数，它用于描述算法执行的时间，用大O符号表述。

时间复杂度和时间频度关系

假设当有一个辅助函数f(n)，使得当n趋近无穷大时，T(n)/f(n)的极限值为不等于0的常数，就叫f(n)为T(n)的同量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的时间渐进复杂度，也就是时间复杂度。

4.1. 推导时间复杂度

根据时间频度T(n)的“三个忽略”原则，可知时间复杂度的特点：

• 忽略所有常数
• 只保留函数中的最高阶项
• 去掉最高阶项的系数

一般求解步骤：

• 找基本语句，通常是最内层循环的循环体。
• 计算基本语句的执行次数的数量级。
• 将基本语句执行次数的数量级放入大Ο记号中。

4.2. 常见时间复杂度

时间复杂度越大，算法的执行效率越低，常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜O(n²)＜…＜Ο(2^n)＜Ο(n!)。

常数阶O(1)

下面代码无论执行多少行赋值和加减，只要没有循环等结构，那这个时间复杂度就都是O(1)，水平面，如：

var i int
j := 20
z := j + i
g := j - i

线性阶O(n)

从下面可看出，a语句时间频度为1，b语句时间频度为n,c语句频度为n,那么T(n) = 1 + n + n = 2n + 1,根据忽略特点，可得T(n) = n,即时间复杂度为O(n) 。

sun := 0 // a
for i := 0; i < n; i++ { // b
 sun = sun + i // c
}

一般来说，只有一个循环结构，输入规模和执行次数都是线性相关的，那么这个代码的时间复杂度就都是O(n) 。

对数阶O(logn)

从下面代码中，语句a时间频度为1，语句b里，在for循环体里，可用公式表示 n = 2^x，x = log2n,T(n) = 1 + log2n,因常数可忽略，因此时间复杂度为O(logn)。

i := 1; // a
for i < n {
i = i * 2  // b
}

线性对数阶O(nlogn)

线性对数阶相当于是上面的对数阶和线性阶的结合，对数阶套了n次循环，相当于 T(n) = n*O(logn)，时间复杂度就是O(nlogn)

for 1 := 1; i < n; i++ {
    j := 1
    for i <= n {
        i = i * 2
    }
}

平方阶O(n²)

平方阶可简单看作是线性阶中又嵌套了一个线性阶，即O(logn)*O(logn)，下面的复杂度就是O(n²)。n次方阶O(n!)的道理同样可这样类推。

for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        sun = j + i
    }
}

5. 空间复杂度

空间复杂度主要指算法或程序运行所需要的存储空间大小，用于对程序运行过程中所需要的临时存储空间的度量.和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示。

5.1. 常见空间复杂度

一般情况，只要算法不涉及到动态分配的空间，以及递归、栈所需的空间，空间复杂度通常为0(1)。一个一维数组，空间复杂度为O(n)，二维数组为O(n^2)。

空间复杂度 O(1)

下面代码中临时空间不会随着n的变化而变化，因此空间复杂度为O(1)

i := 1; // a
for i < n {
i = i * 2  // b
}

空间复杂度 O(n)

下面代码中，只有for循环内每次循环赋值一次，因此，对应的空间复杂度为 O(n)。

sun := make([]int)
for i := 0; i < n; i++ {
 sun[i] = 2 * i
}

6. 复杂度的四个概念

• 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示
• 最好情况时间复杂度：代码在最好情况下执行的时间复杂度。
• 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。
• 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

例如：

针对排序的几种算法的时间复杂度对比。