北大硕士LeetCode算法专题课---算法复杂度介绍

末蓝、 2024-03-30 16:28 59阅读 0赞

## 算法复杂度中大O的含义 ##

推荐教程：[北大硕士带你手撕Leetcode算法题][Leetcode]

**大****O****复杂度表示法**

算法面试中， 经常会被问到，你写的算法复杂度是多少， 或者设计一个复杂度为 O(nlogn) 的算法复杂度分析是估算算法执行效率的方法，公式O(f(n))表示算法的复杂度，此方法即为大O复杂度表示法O(f(n))中n表示数据规模，f(n)表示运行算法所需要执行的指令数。

**下面的代码非常简单,求 1,2,3…n 的累加和，我们来估算它的执行效率**

![191bfee830664cb4ae81b0723eec40e6.png][]

假设每行代码执行的时间都一样为t：

•执行第2行代码需要时间t，第3,4行代码运行了n遍，需要的时间为2n\*t

•这段代码总执行时间为（2n+1）\* t

结论：代码执行的总时间T(n)与每行代码的执行次数成正比

**看下面的代码，估算该段代码的执行时间**

![2062adc22de24b11bccb354a493f1fa9.png][]

同样假设每行代码执行的时间都一样为t：

•执行第2行代码需要时间t

•第3行代码运行了n遍，需要时间为n\*t

•第4、5行代码运行了n2次，需要时间为2n2 \* t

•执行所有代码的总时间为 （2n2 \+ n + 1）\* t

结论：代码执行的总时间T(n)与每行代码的执行次数成正比

用O(f(n))来表示算法复杂度

![673dff17ab634896aff3abc89ffa97f9.png][]

T(n) = O(f(n)) , O表示代码的执行时间T(n) 与 f(n)表达式成比例。

大O复杂度表示法：上面例子中的T(n) = O(2n+1), 另一个  T(n) = O(2n2 \+ n + 1)。

大O时间复杂度并不表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫作渐进时间复杂度

（asymptotic time complexity），简称时间复杂度

当数据量特别大， 也就是n的取值很大的时候，大O表示法中低阶、常量、系数三部分并不会左右增长趋势，可以忽略

![2f69d1ed81b2415fafd7ded738620efa.png][]

上面例子中的T(n) = O(2n+1), 另一个  T(n) = O(2n2 \+ n + 1)

用大O表示法表示上面两段代码的时间复杂度，可以记为O(n)，O(n2)

![6e792baca9c54e13918096939637a1d7.png][]

**数据规模**

通过下面的例子，我们来体会一下数据规模对程序运行时间的影响

![4c15ff564e78440ab896f3181c10adff.png][]

通过刚才的例子我们可以得出如下结论，如果想在1s之内解决问题

O(n2) 的算法可以处理大约104级别的数据

O(n) 的算法可以处理大约108 级别的数据

O(nlogn)的算法可以处理大约107级别的数据

**有的时候，自己写的算法认为是O(nlogn), 但是在线判题系统提示超时，可以先估计一下，前面提到标准降低一个数量级**

O(n2) 的算法可以处理大约103级别的数据

O(n) 的算法可以处理大约107 级别的数据

O(nlogn)的算法可以处理大约106级别的数据

自己写代码实验，数据每增加一个数量级看看耗时的变化

**空间复杂度**

解决问题时，多创建了一个数组：O(n)

解决问题时，多创建了一个二维数组：O(n2)

解决问题时，用到了几个临时的变量：O(1)

![53ce3a613a1a499793973cbc78c67989.png][]

**时间复杂度分析**

如何分析一段代码的时间复杂度？

**1.在分析一个算法、一段代码的时间复杂度时，只关注循环执行次数最多的那一段代码就可以了**

![494d5f38c679469a8f6cdea3f6e21f3a.png][]

上面的代码中，我们只需要关注内层for循环的时间复杂度就可以了

内层for循环的两行代码被执行了n2次，所以总的时间复杂度就是O(n2)

**2.总复杂度等于量级最大的那段代码的复杂度**

![6690188f30f14620887708e2a14a2601.png][]

上面的代码分为两部分，分别是求 sum\_、sum\_1

计算sum\_部分的代码段时间复杂度O(n)，计算sum\_1部分的代码段时间复杂度为O(n2)

总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(n2)

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

![2bb0f672cd5b4f2fb372ae258db03d9e.png][]

上面的代码中第二个函数调用了第一个函数, 如果把fn函数调用当作一个普通操作, 那么第二个函数的时间复杂度为O(n)

Fn函数的时间复杂度为O(n)，那么函数整体的时间复杂度为O(n\*n) = O(n2)

**4. 当两段代码的数据规模不同时，不能省略复杂度低的部分**

![5f55949a38614d09b857466378f87032.png][]

上面的代码分为两部分，分别是求 sum\_、sum\_1

计算sum\_部分的代码段时间复杂度O(n)，计算sum\_1部分的代码段时间复杂度为O(m2)

总的时间复杂度由复杂度最大的部分决定, 所以上面代码复杂度为O(m2\+n)

需要注意的地方：

看见双重for循环，算法的复杂度一定是O(n2)么？

![58694d386e0a4b49838dfc171ecec928.png][]

**关于O(logn)**

![41cad8e3eb7b408fa6708e3f6f2612b6.png][]

![a0e02b6e498d44a9882550a0ad1e6d03.png][]

![a2f0e8d6f2494432be603837a921df7c.png][]

![8ceed4ffbf6044418139f567ca74fca4.png][]

上面代码的时间复杂度 O(logn)

n 经过几次“÷10”=0 → log10n = O（logn)

关于O(logn)

logaN logbN 之间是什么关系？

logaN = logab \* logbN

上面式子当中，logab 为常数，可以忽略

下面代码的复杂度：O(n2)

![183f11f9732c4016b033e26e95a5d9e8.png][]

**简单复杂度分析:**

① 关注循环执行次数最多的那一段代码

② 总复杂度等于量级最大的那段代码的复杂度

③ 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

④ 当两段代码的数据规模不同时，不能省略复杂度低的部分

⑤ 复杂度中对数的部分通常忽略底数

**递归算法复杂度分析**

在递归中只做了一次递归调用时间复杂度：O(logn)

![4cfdf2369b734672bb586bbd6208b2cd.png][]

在递归中只做了一次递归调用

递归深度为D

在每个递归函数中， 时间复杂度为T

总体时间复杂度为O(T\*D)

![83e2135f45214b0080ca474cb62ff9af.png][]

![58adbd749ebf4d029b39d6ec6267816d.png][]

![c516db225c1340339830f70863e9dbe4.png][]

![42872c12663e42efa5efeb5922312624.png][]

**最好、最坏、平均时间复杂度分析**

算法复杂度在有些情况下是用例相关的

插入排序算法O(n2) 最好情况：O(n)

快速排序算法O(nlogn) 最差情况：O(n2)

算法面试复杂度分析一般指的就是平均情况

**均摊复杂度分析**

某些复杂耗时操作是为了辅助其它操作，可以将这个复杂操作的时间平摊到其它操作中

![0d431ab96b3d4b378cc3b803515b0b69.png][]

每一次添加耗时O（1）， 初始长度填满之后，再添加1个元素，此时需要开辟一块长度为2n的新的空间，并将之前的N个元素复制过来，这一步的操作复杂度为n，平均来看 O（2）

**均摊复杂度：就是把过程复杂操作所耗费时间分担到简单操作上**

对一个数据结构进行一组连续操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，适合运用均摊复杂度分析代码

[Leetcode]: http://yun.itheima.com/course/1005.html?capid=1
[191bfee830664cb4ae81b0723eec40e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bf947490d43c49bba28ab3ad85f08ef0.png
[2062adc22de24b11bccb354a493f1fa9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8165b0c1a31b4a1db27eca38a3c39491.png
[673dff17ab634896aff3abc89ffa97f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6adc657ecdfb452890eb2d697657894d.png
[2f69d1ed81b2415fafd7ded738620efa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ed08ccbfadb340e5ab17014c77ebc76a.png
[6e792baca9c54e13918096939637a1d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/156fa12426cc46ca9df971e18d5b180e.png
[4c15ff564e78440ab896f3181c10adff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/689e21a5cb0748cb87869404451f4ac5.png
[53ce3a613a1a499793973cbc78c67989.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/321741f3b5ed4feb80cab7d6b1447c79.png
[494d5f38c679469a8f6cdea3f6e21f3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/22beb2eaf72b4b10a6817a3ed6abc183.png
[6690188f30f14620887708e2a14a2601.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8e7c49bf293a41689988ee498d749e3b.png
[2bb0f672cd5b4f2fb372ae258db03d9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e26d4fb672e04d22ab481776c98a1b3d.png
[5f55949a38614d09b857466378f87032.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d9f8b8adef8b48c38622c2c0c05719b4.png
[58694d386e0a4b49838dfc171ecec928.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/27ad90477e404a0e8126396730a4e0f6.png
[41cad8e3eb7b408fa6708e3f6f2612b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/505ff6f9cf4a4e79b43f6c43f03383a6.png
[a0e02b6e498d44a9882550a0ad1e6d03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8e67be6e66b74cf7a3201314b46ae036.png
[a2f0e8d6f2494432be603837a921df7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f6e119ed95784f7c97b15a3def5d294b.png
[8ceed4ffbf6044418139f567ca74fca4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d0fd9fae1b784b96be7f0cd49ba4281c.png
[183f11f9732c4016b033e26e95a5d9e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c16489bbc8f54fc4ad686549b9b8e680.png
[4cfdf2369b734672bb586bbd6208b2cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/90f2756daba74dfe9b2119c710274a81.png
[83e2135f45214b0080ca474cb62ff9af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/486bfa982f324dd7be462d5ab8876fef.png
[58adbd749ebf4d029b39d6ec6267816d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/122f899c05a3493abc156bf2eb6151d6.png
[c516db225c1340339830f70863e9dbe4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/85ae0a97736641a8b7b48b5ad3ab93b0.png
[42872c12663e42efa5efeb5922312624.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3b397a75c55b4cb3bfb4f09082c468c9.png
[0d431ab96b3d4b378cc3b803515b0b69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/edcc5ccaba6449b9850d75789e3eb3a6.png