1.1 时间和空间复杂度分析

最常见的时间复杂度就是下面 7 种

• O(1)：常熟复杂度

• O(log n)：对数复杂度

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

• O(n^2)：平方

• O(n^3)：立方

• O(2^n)：指数

• O(n!)：阶乘

我们怎么来看这个时间复杂度呢？

最常用的方式就是直接看这个函数，或者是说这段代码他根据 n 的不同情况他会运行多少次

如下图代码：

O(1)

这段代码不管 n 等于多少，他的程序只执行一次，也就是说它只会执行一次 println:Hey - your input is：所以他的时间复杂度就是 O(1)

O(1)

这串代码我们不关心前面的常数系数，也就是说该代码虽然会执行 3 次，但是不管 n 是多少他只执行三次所以他的时间复杂度还是常数。还是 O(1)，因为他们都是常数级

O(n)

i = 1 然后一直循环到 n ，这里我们会发现虽然他只有三行代码，主要的 println 语句虽然只有一句，但是这段代码就发生了变化。当 n = 1 的时候执行一次，但是当 n = 100 次的时候就会执行 100 次，所以的话随着 n 的不同，这段语句它执行的次数也会不一样。

所以我们会看到他的时间复杂度和 n 是线性关系，所以我们就记位 O(n)。n 等于多少的话，他的运行复杂度就是 n 的一次方

思考题：

请看下面代码他的时间复杂度是多少

package main
​
import (
    "fmt"
)
​
func main() {
    n := 20
    for i := 1; i <= n; i++ {
        fmt.Println("hello world")
    }
​
    for j := 1; j <= n; j++ {
        fmt.Println("hello jjjj")
    }
}

答：即使他们是并列的，那么就相当于 2 的 n 次，前面的常数系数我们不关心，所以的话像上面这段代码的话，就是 O(n) 的时间复杂度

O(n^2)

所以同理如果在是一个 嵌套型的循环的话，你会发现如果 n = 100 的话，println 这个语句就会执行 100 * 100 = 100000 所以他的时间复杂度就是 O(n^2)

O(log(n))

接下来我们看上图代码，这段代码我们会发现如果 n 等于 100 的话，他会执行几次呢？只会执行 10 次，因为 10 * 10 = 100

这个函数体执行的次数永远是他的 log(2n)，所以他的时间复杂度就是 O(logn)

O(k^n)

这个斐波那契值，它的求第 n 项的话，他这里用了一种递归的形式，那么这就是牵扯到了递归程序在执行的时候，怎么计算他的时间复杂度。他的答案是 K 的 n 次方，这里的 k 是一个常数，所以简单的递归求斐波那契值的话他是非常慢的，指数级的时间复杂度。

1.2 时间复杂度曲线

我们从上图可以看到， n 如果比较小的时候，在 5 以内的话不同的时间复杂度其实都差不多。但是如果当 n 开始扩大，我们会发现指数级的话它涨的非常快。也就是说在写程序的时候能够优化时间复杂度，比如说从 2 的 n 次方降到 n 平方的话，那么从这个曲线来看的话当 n 在较大的时候得到的收益是非常高的。

总结：

• 在写程序的时候一定要对自己的程序的空间复杂度和时间复杂度有所了解，而且是养成习惯，写完了程序之后能够下意识的分析出时间复杂度和空间复杂度

• 能够用最简洁的时间复杂度和空间复杂度完成这段程序的话，是顶尖职业选手的素养

1.3 例子

• 方法一：我们用的就是暴力求解，时间复杂度为 O(n)

• 方式二：我们用了一个数学公式，时间复杂度为 O(1)，因为这一段语句永远都只执行了一次

所以我们可以看出程序执行的方法不同，但是得到的结果是一样的，但是他的复杂度会很不一样。

总结：

但我们看到一个题时候，我们要想所有可能解决的方法，这时候不是第一个方法，就是所有的解决方法，同时比较这些方法的时间复杂度和空间复杂度。

一个好的时间复杂度的程序，会让你的程序跑起来更快更节约资源。

最后再找出最优的解决方案，也就是时间最快的解决方案，内存的话用的最少的更好

1.4 更复杂的情况：递归

如果是在递归条件下的话，怎么来分析时间复杂度。递归的话我们关键要了解他的递归总共执行了这个语句多少次。如果是循环的话就比较好理解，n 次的循环就是 n 次。

递归的话其实他层层嵌套下去怎么办呢？

其实很多时候我们要借助就是把递归他的执行顺序画出这么一个树形结构，我们称之为它的递归状态的递归树。

看下面这个案例：

求斐波那契数列的第 n 项，斐波那契的递推公式：fn = f(n - 1) +f(n -2)

函数递归：

这段语句他的时间复杂度是多少我们来分析一下，这个代码是 2 的 n 次方，或者说是 k 的 n 次方。

假设这个时候我们的 n 取 6 ，要计算 f(6) 我们就得看这个程序怎么执行，如下图：

• 这个时候就会 return f(5) + f(4) 所以要计算 f(6) 就引出两个分支

• 分别是 f(5) 和 f(4)，所以就会发现要计算 f(6) 至少是要多出两次的计算

• 然后要算 f(5) 和 f(4) ，就同理可得依此类推

• 这里我们就可以看到两个现象

  • 第一个现象的话就是它每多展开一层的话，运行的节点数就是上一层的两倍，第一层只有一个节点，第二层就有两个节点，第三次的话就会有 4 个节点，然后再写一层就是 8 个节点也就是 2 的三次方，依此类推所以的话他的每一层节点数也就是它的执行次数的话是按照指数级递增。所以由此可见最后一层就是 2 的 n 次方。

  • 第二个现象我们可以观察的是有重复的节点出现在我们的状态树里，比如说右上角的 f(4) 和左下角的 f(4) ，他们是重复的，同时 f(3) 的话在这里也重复了

• 我们继续把状态树依此类推的展开，最后的树型结构就如图，因为最后每个分支都要走到 f(0) 和 f(1)，这两个初始值，这时我们会发现在图中有很多次重复的 f(n) 出现，正是因为有这么多大量的冗余计算，导致求第 f(6) 的斐波那契值就变成了 2 的 6 次方这么一个反复的时间复杂度。时间复杂度为 O(n^2)

package main
​
import (
    "fmt"
)
​
func f(n int) int {
    // n 为 6 肯定不小于等于 2 所以不满足
    if n <= 2 {
        return 1
    }
​
    return f(n-1) + f(n-2)
}
​
func main() {
​
    res := f(6)
    fmt.Println(res)
}

动态规划：

当然我们可以用动态规划，一个 for 循环就能够解决此问题，res 每次记录下一个数的和，时间复杂度为 O(n)

package main
​
import (
    "fmt"
)
​
func f(n int) int {
    if n <= 2 {
        return 1
    }
    f1 := 1
    f2 := 1
    res := 0
    for i := 3; i <= n; i++ {
        res = f1 + f2
        f1, f2 = f2, res
    }
    return res
}
​
func main() {
​
    res := f(6)
    fmt.Println(res)
}

1.5 主定理

主定理：用来解决所有递归函数，怎么来计算他的时间复杂度。

也就是说，任何一个分治或者是递归的函数，都可以算出他的时间复杂度，就是通过这个主定理

主定理主要分为四种：

1. 二分查找（Binrary Search）：一般发生在一个数列本身有序的时候，需要在有序的数列里面找到你想要的目标数，所以他每次都将有序数组一分为二，之查找一边这么查下去的话他的时间复杂度为 log(n) 的复杂度，

   如果是一维数组进行二分查找就是 O(logn)

2. 二叉树（Binary tree traversal）：如果是二叉树的遍历的话他就是 O(n)，因为通过主定理我们可以知道他每次要一分为二，但是每次一分为二之后每一边他是相同的时间复杂度这么下去，最后他的递推公式就变成了图中T(n) = 2T(n/2) + O(1) 这样，最后的话用主定理可以推算出他的运行时间为 O(n)，

   可以简化推算，二叉树的遍历的话，我们会每一个节点都访问一次，且仅访问一次，所以他的时间复杂度就是 O(n)

3. 排序矩阵搜索（Optimal Sorted matrix search）： 第三种情况就是在一个排好序的二维矩阵中进行二分查找这个时候怎么办呢？同理主定理可以得出时间复杂度时 O(n) 的

   如果是二维的有序矩阵进行查找同理，这时候就被降了一维就不是 n 平方的算法，而是 O(n) 的算法

4. 归并排序（Merge Sort）：在排序中经常使用的叫做归并排序，所有排序最优的办法就是 nlogn

1.5.1 思考题

1.5.1.1 二叉树遍历时间复杂度

二叉树遍历 – 前序、中序、后序：时间复杂度是多少？

这个时间复杂度就是 O(n) ，这个 n 代表二叉树里面的数的节点总数。

通过主定理这么得到的，不管前序中序后序它遍历二叉树的时候，每个节点会访问一次且仅访问一次，所以他的时间复杂度，就是线性于二叉树的节点总数。

也就是 O(n) 的时间复杂度

1.5.1.2 图的遍历时间复杂度

图的遍历也同理可得，里面的每个节点访问一次仅访问一次，所以时间复杂度为 O(n) ,n 为图里面的节点总数。

1.5.1.3 搜索算法：DFS,BFS 时间复杂度是多少

搜索算法 DFS 深度优先 BFS 广度优先，关于这两个深度优先和广度优先算法的话 ，也就是不管深度优先广度优先，因为访问的节点是访问一次，所以他的时间复杂度都是 O(n) ，这里的 n 指的是搜索空间里面的节点总数。

1.5.1.4 二分查找：时间复杂度是多少

时间复杂度为 logn

1.6 总结

• 常见的时间、空间复杂度