后浪笔记一零二四

时间复杂度分析

如何实时地统计业务接口的 99% 响应时间？

  • 每次查询时，从小到大排序所有的响应时间，如果总共有 1200 个数据，那第 1188 个数据就是 99% 的响应时间。每次统计都要执行一遍排序，效率太低。
  • 使用两个堆可以非常高效地解决这个问题。

这就是数据结构的力量。

数据结构和算法的圣经：

大 O 复杂度表示法

举个例子，求 1,2,3…n 的累加和：

1
2
3
4
5
6
7
8

1 func cal(n int) int {
2         sum := 0
3         i:=1
4         for ; i<=n; i++ {
5                 sum += i
6         }
7         return sum
8 }

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time。在这个假设的基础之上，这段代码的总执行时间是多少呢？

第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+2)*unit_time。

按照这个分析思路，我们再来看这段代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

 1 func cal(n int) int {
 2         sum := 0
 3         i:=1
 4         j:=1
 5         for ; i<=n; i++ {
 6                 j=1
 7                 for ; j<=n; j++ {
 8                         sum += i*j
 9                 }
10         }
11         return sum
12 }

第 2、3、4 行代码，每行都需要 1 个 unit_time 的执行时间，第 5、6 行代码循环执行了 n 遍，需要 2n * unit_time 的执行时间，第 7、8 行代码循环执行了 n^2遍，需要 2n^2 * unit_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n^2+2n+3)*unit_time。

尽管我们不知道unit_time的具体指，但是通过这两段代码执行时间的推到过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间T(n)与 每行代码的执行次数累加和f(n) 成正比。

我们可以把这个规律总结成一个公式： $T(n)=O(f(n))$

其中，T(n) 我们已经讲过了，它表示代码执行的时间；n 表示数据规模的大小；
f(n) 表示每行代码执行次数的累加和。
公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

所以，第一个例子中的 T(n) = O(2n+2)，第二个例子中的 T(n) = O(2n^2+2n+3)。这就是 大 O 时间复杂度表示法。

当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n^2)。

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码 在采用大 O 标记复杂度的时候，可以
  • 忽略系数，即 O(Cf(n)) = O(f(n))
  • 忽略常数、低阶，例如 O(2n^2+2n+3) = O(n^2)
  1. 加法法则：总复杂度等于量级最大的那段代码的复杂度 我们将这个规律抽象成公式就是：

如果 $T1(n)=O(f(n))，T2(n)=O(g(n))$；
那么 $T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))$

  1. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积 我们将这个规律抽象成公式就是：

如果 $T1(n)=O(f(n))，T2(n)=O(g(n))$；
那么 $T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).$

也就是说，假设 T1(n) = O(n)，T2(n) = O(n^2)，则 T1(n) * T2(n) = O(n^3)。落实到具体的代码上，我们可以把乘法法则看成是嵌套循环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

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

几种常见时间复杂度实例分析

如下列出了几乎涵盖了可以接触的所有代码的复杂度量级：

  • 常量阶： O(1)，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)
  • 对数阶： O(logn)
  • 线性阶： O(n)
  • 线性对数阶： O(nlogn)
  • 平方阶： O(n^2)， 立方阶：O(n^3)，…，k次方阶：O(n^k)
  • 指数阶： O(2^n)
  • 阶乘阶： O(n!)

这些复杂度量级分为 多项式量级 和 非多项式量级 ，其中，非多项式量级只有两个：O(2^n)和O(n!)。我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。

当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

O(logn)、O(nlogn)

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。举个例子，计算如下代码的时间复杂度：

1
2
3
4
5
6
7

1 func cal(n int) int {
2         i := 1
3         for ;i<=n; {
4                 i = i * 2
5         }
6         return i
7 }

上面的代码中，第三行代码是循环执行次数最多的，所以只要计算出这行代码执行了多少次，就可以知道整段代码的时间复杂度。

从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。所以i的值依次是：

2^0, 2^1, 2^2, ..., 2^k, ..., 2^x=n

所以，只要知道x的值是多少，就知道这行代码执行的次数了。因为2^x=n，所以$x=log_2n$

而下面这段代码的时间复杂度是 $O(log_3n)$：

1
2
3
4
5
6
7

1 func cal(n int) int {
2         i := 1
3         for ;i<=n; {
4                 i = i * 3
5         }
6         return i
7 }

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。为什么呢？

因为对数之间是可以相互转换的，$log_3 n$ 就等于 $log_3 2 * log_2 n$，所以 $O(log_3 n) = O(C * log_2 n)$，

如果一段代码的时间复杂度是 $O(logn)$，我们循环执行n遍，时间复杂度就是$O(nlogn)$。

$O(nlogn)$是一种非常常见的算法时间复杂度，比如，归并排序、快速排序的时间复杂度都是 $O(nlogn)$。

O(m+n)、O(m*n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func cal(m, n int) int {
        sum_1 := 0
        i := 1
        for ;i<m;i++ {
                sum_1 += i
        }

        sum_2 := 0
        j := 1
        for ;j<n;j++ {
                sum_2 += j
        }

        return sum_1 + sum_2
}

从代码中可以看出，我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

 1 func PPrint(n int) {
 2         i := 0
 3         a := make([]int, n)
 4         for ;i<n; i++ {
 5                 a[i] = i*i
 6         }
 7
 8         for i=n-1; i>=0; i-- {
 9                 println(a[i])
10         }
11 }

可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。

常见的空间复杂度就是 O(1)、O(n)、O(n^2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

最好、最坏情况时间复杂度和平均时间复杂度

1
2
3
4
5
6
7
8

func find(array []int, n, x int) int {
        i := 0
        pos := -1
        for ; i<n; i++ {
                if array[i] == x { pos = i }
        }
        return pos
}

这段代码要实现的功能是，在一个无序的数组（array）中，查找变量x出现的位置。如果没有找到，就返回-1。这段代码的时间复杂度是O(n)，n代表数组的长度。

我们在数组中查找一个数据，并不需要每次都把整个数组都遍历一遍，因为有可能中途找到就可以提前结束循环了。所以可以这样优化代码：

1
2
3
4
5
6
7
8

func find(array []int, n, x int) int {
        i := 0
        pos := -1
        for ; i<n; i++ {
                if array[i] == x { pos = i; break }
        }
        return pos
}

这个时候，用前面的知识就无法计算时间复杂度了，因为要查找的变量 x 可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。所以，不同的情况下，这段代码的时间复杂度是不一样的。

为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

最好情况时间复杂度、最坏情况时间复杂度比较容易分析，我们重点研究平均时间复杂度。

要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以 n+1，就可以得到需要遍历的元素个数的平均值，即：

$${{1+2+3+…+n+n}\over{n+1}} = {{n(n+3)}\over{2(n+1)}}$$

我们知道，时间复杂度的大 O 标记法中，可以省略掉系数、低阶、常量，所以，咱们把刚刚这个公式简化之后，得到的平均时间复杂度就是 O(n)。

这个结论虽然是正确的，但是计算过程稍微有点儿问题。究竟是什么问题呢？我们刚讲的这 n+1 种情况，出现的概率并不是一样的。我带你具体分析一下。

我们知道，要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便计算，我们假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0～n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0～n-1 中任意位置的概率就是 1/(2n)。

因此，前面的推导过程中存在的最大问题就是，没有将各种情况发生的概率考虑进去。如果我们把每种情况发生的概率也考虑进去，那平均时间复杂度的计算过程就变成了这样：

1*(1/2n) + 2*(1/2n) + 3*(1/2n) +...+ n*(1/2n) + n*(1/2) = (3n+1)/4

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

均摊时间复杂度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 这个例子并不高效，实际上没人会这么写
var array = make([]int, 10)
var count = 0

func insert(val int) {
        if count == len(array) {
                sum := 0
                for i:=0; i<len(array); i++ {
                        sum += array[i]
                }
                array[0] = sum
                count = 1
        }
        array[count] = val
        count++
}

这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是代码中的 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组的第一个位置，然后再将新的数据插入。但如果数组一开始就有空闲空间，则直接将数据插入数组。

最好情况时间复杂度：最理想的情况下，数组中有空闲空间，我们只需要将数据插入到数组下标为 count 的位置就可以了，所以最好情况时间复杂度为 O(1)

最坏情况时间复杂度：最坏的情况下，数组中没有空闲空间了，我们需要先做一次数组的遍历求和，然后再将数据插入，所以最坏情况时间复杂度为 O(n)

平均时间复杂度：O(1)

假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 O(n)。而且，这 n+1 种情况发生的概率一样，都是 1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：

1*(1/n+1)+1*(1/n+1)+...+1*(1/n+1)+n*(1/n+1) = (2n/n+1) = O(1)

insert函数和之前的find函数的区别：

  1. find() 函数在极端情况下，复杂度才为 O(1)。但 insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高，为 O(n)。
  2. 对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

针对这种特殊的场景，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度我们起了一个名字，叫均摊时间复杂度。

我们还是继续看在数组中插入数据的这个例子。每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件

如何编写递归代码？
假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？

  • 写出递推公式，找到终止条件 
    f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)
  • 将递推公式转化为代码
  • 注意事项：

    • 警惕堆栈溢出：因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。所以，如果最大深度比较小，比如 10、50，就可以使用递归。

    • 警惕重复计算：从下图可以看出重复计算了两次f(3)和f(4)

                  / f(2)
        f(4)
        /   \ f(3)
f(6)       
        \   / f(3)
        f(5)
            \ f(4)
      • 为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

      // 递归实现斐波那契数列
type Fibs struct {
        val map[int]int // 使用字典存储结果
}

func NewFibs(n int) *Fibs {
        return &Fibs{
                make(map[int]int, n),
        }
}

func (fib *Fibs) Fibonacci(n int) int {
        if n <= 1 {
                return 1
        }
        if n == 2 {
                return 2
        }
        if fib.val[n] != 0 {
                return fib.val[n]
        }
        res := fib.Fibonacci(n-1) + fib.Fibonacci(n-2)
        fib.val[n] = res
        return res
}

处理递归的正确思维方式：

  • 错误的思维方式：对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区。
    当我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。
  • 如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。
    这样，就只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。
  • 正确的思维方式：只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

用递归实现阶乘：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

type Fac struct {
    val map[int]int
}

func  NewFactorial(n int) *Fac {
    return &Fac{
        make(map[int]int, n),
    }
}

func (fac *Fac) Factorial(n int) int {
    if fac.val[n] != 0{
        return fac.val[n]
    }

    if n <= 1{
        fac.val[n] = 1
        return 1
    }else {
        res := n * fac.Factorial(n-1)
        fac.val[n] =res
        return res
    }
}

用递归实现全排列:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

type RangeType struct {
    value []interface{}
}

func NewRangeArray(n int) *RangeType  {
    return &RangeType{
        make([]interface{},n),
    }
}

func (slice *RangeType)RangeALL(start int)  {
    len := len(slice.value)
    if start == len-1{
        // 如果已经是最后位置，直接将数组数据合并输出
        fmt.Println(slice.value)
    }

    for i:=start; i<len; i++{
        // i = start 时输出自己
        // 如果i和start的值相同就没有必要交换
        if i==start || slice.value[i] != slice.value[start]{
            //交换当前这个与后面的位置
            slice.value[i], slice.value[start] = slice.value[start], slice.value[i]
            //递归处理索引+1
            slice.RangeALL(start+1)
            //换回来，因为是递归，如果不换回来会影响后面的操作，并且出现重复
            slice.value[i], slice.value[start] = slice.value[start], slice.value[i]
        }
    }
}

func permute(num []int) [][]int {
        if len(num) == 1 {
                return [][]int{num}
        }
        ret := make([][]int, 0)
        for i, x := range num {
                num2 := make([]int, 0)
                num2 = append(num2, num[:i]...)
                num2 = append(num2, num[i+1:]...)
                tmp := permute(num2)
                for _, v := range tmp {
                        sub := []int{x}
                        sub = append(sub, v...)
                        ret = append(ret, sub)
                }
        }
        return ret
}

func TestRangeALL(t *testing.T) {
    slice1 := NewRangeArray(4)
    for i:=0; i<4; i++{
        slice1.value[i] = i+1
    }
    slice1.RangeALL(0)

    slice2 := NewRangeArray(3)
    slice2.value[0] = "a"
    slice2.value[1] = "b"
    slice2.value[2] = "c"
    slice2.RangeALL(0)

}

专题: 时间复杂度分析

本文发表于 2021-07-15，最后修改于 2021-07-15。

本站永久域名「 jiavvc.top 」，也可搜索「 后浪笔记一零二四 」找到我。

上一篇 « 动态规划 Dynamic Programming 下一篇 » yaml语法

赞赏支持

请我吃鸡腿 =^_^=

i ysf

云闪付

i wechat

微信

推荐阅读

栈

发表于2021-07-15， 阅读约4分钟

Untitled

发表于0001-01-01， 阅读约1分钟

Untitled

发表于0001-01-01， 阅读约11分钟

Big Image