算法复杂度分析

我们都知道软件开发，数据结构、算法都是我们绕不过的知识点，而它们都是为了解决“快”和“省”的问题。所以我们怎么去衡量我们写出来的代码既快又省呢？这里就要用我们这篇文章说的两个复杂度来说明了。

复杂度分析

写出来的代码，通过一些监控、统计，就可以知道我们的程序执行时间以及所占用的内存大小等，但是这些监控、统计是建立在我们运行程序的基础上的，而且与我们运行的环境、数据量的大小、数据的随机性等等因素有密切的关系，我们很难保证代码上到线上就如我们所想那样速度非常而且占用内存小。
所以我们就需要有一种建立在程序无需运行的基础上的机制来帮助我们粗略估算程序有“多快”“多省”。

大 O 复杂度表示法

我们先来看以下代码：

func cal(n int) int {result := 0for i := 0; i <= n; i++ {result += i}return result
}

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。
我们假设对每行代码的执行都是一样的时间，假设为 time_stamp。
第 1 行代码需要 1 个 time_stamp 的执行时间，第 2、3 行都运行了 n 遍，所以需要 2n*time_stamp 的执行时间，所以这段代码总的执行时间就是 (2n+1)*time_stamp。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。
那么我们就可以总结出来一个公式了：
T(n)=O(func(n))
解释一下这个公式：T(n) 它表示代码执行的时间；n 表示数据规模的大小；func(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 func(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 func(n) 表达式成正比。

时间复杂度

那我们来看看如何分析一段代码的时间复杂度。

1. 关注循环执行次数最多的代码

如下代码

func cal(n int) int {result := 0for i := 0; i <= n; i++ {result += i}return result
}

这段代码执行次数实际由传入的 n 来计算，这个时候我们就认为这是跟 n 线性增长的，则此段代码的时间复杂度为 O(n)。

2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

如下代码：

func cal(n int) {sum_1, a := 0, 1for a <= 100 {sum_1 += a}sum_2, b := 0, 1for b <= n {sum_2 += b}sum_3 := 0for i := 1; i <= n; i++ {for j := 1; j < n; j++ {sum_3 += i + j}}
}

这段代码分为三部分。我们可以分别分析每一部分的时间复杂度，然后把它们放到一块儿，再取一个量级最大的作为整段代码的复杂度。
第一个 for 循环就执行了 100 次，和 n 无关，所以是常量级的 O(1)。
第二个 for 循环根据传入的 n 来进行执行，所以是线性级别的 O(n)。
第三个 for 循环有嵌套循环，所以是平方级别的 O(n^2)。
综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n^2)。

3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

也就是说，假设 T1(n) = O(n)，T2(n) = O(n2)，则 T1(n) * T2(n) = O(n3)。可以把乘法法则看成是嵌套循环。

func func4(n int) int {sum := 0for i := 1; i < n; i++ {for j := 1; j < n; j++ {sum = sum + i}}return sum
}

常见的时间复杂度

O(1)：常数复杂度

n:=1000
fmt.Println("input :",n)

O(log n)：对数复杂度

for i <= n {i = i * 2
}

O(n)：线性时间复杂度

for i := 0; i <= n; i++ {fmt.Println("i : ", i)
}

O(n^2)：平方

for i := 0; i <= 100; i++ {for j := 0; j <= 100; j++ {fmt.Printf("i : %d, j : %d\n", i, j)}
}

空间复杂度

表示算法的存储空间与数据规模之间的增长关系。

空间复杂度就没有时间复杂度那么多变、复杂了，主要是观察函数中创建对象的多少。

比如如下代码：

func func5(n int) int {var i, count = 1, 0for i <= n {i = i * 2count++}return count
}

从第二行来看，我们就只申请了 i 、 count 两个变量的内存，那么我们就可以认为这段函数的空间复杂度为常量级别的，也就是我们所说的 O(1)。

常见的空间复杂度

我们常见的空间复杂度就是 O(1)、O(n)、O(n^2)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。