Big O

image.png
image.png

时间复杂度

时间复杂度是指执行算法所需的计算工作量。一般来说，计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做T(n)=O(f(n));
常见时间复杂度有:常数阶、线性阶、平方阶、立方阶、对数阶、nlog2n阶、指数阶
效率：O(1) > O(log2n)> o(n)> o(nlog2n) > o(n^2) > o(n^3) > o(2^n) > o(n!) > o(n^n) 如果有多个复杂度，只取复杂度最高的值。 达到o(n^2)的算法基本是不可用的

image.png
image.png
image.png
答案：O(1)
image.png
如果 内层循环的 n 改为 m，那么可以表示成 O(N*M)，也可以表示成 O(N^2)，两者的复杂度差不多。

image.png

空间复杂度

空间复杂度是指执行这个算法所需要的内存空间。

斐波那契的复杂度

  • O(2^n)

image.png
image.png

常见数据结构复杂度

image.png

数组排序算法复杂度

image.png

常见算法复杂度

image.png

递归算法的时间复杂度？

  • 二分法：时间复杂度为 O(logn)
  • 递归：时间复杂度本质上是要看 递归的次数 * 每次递归中的操作次数
  • 一层 for 循环：时间复杂度为 O(n)
  • for 循环内执行算法：在 for 循环内执行算法，那时间复杂度就是 O(n) * O(操作的时间复杂度)
    • for 循环遍历 + 二分法：时间复杂度为 O(nlogn)；

image.png

注意事项

算法时间复杂度抉择（前端重时间，轻空间）

内置API的时间复杂度（如arr.unshift)

数组是一个有序结构：

  • push：只需要往数组末尾添加元素即可。时间复杂度为 O(1)
  • unshift：不是直接在数组前列添加一个元素就行了。可以理解为：需要将数组的的每个元素都往后迁移，才能在最前列让出一个空的位置。所以时间复杂度为 O(n)
  • includes：看调用方是什么样的值，如果是 ‘123456’.includes(3) 这种，就不需要考虑时间复杂度，因为值是已知的，计算量很短，如果是未知的数据，那么就需要考虑时间复杂度。
  • splice：时间复杂度为 O(n)；
  • sort：时间复杂度为 O(nlogn)；

参考

https://www.bigocheatsheet.com/
如何理解算法时间复杂度的表示法，例如 O(n²)、O(n)、O(1)、O(nlogn) 等？

https://zhuanlan.zhihu.com/p/143358017
https://segmentfault.com/a/1190000016168727
https://juejin.cn/post/6844904103194132494
https://juejin.cn/post/6844903750985842695

对数公式
算法复杂度中的O(logN)底数是多少