常见时间复杂度

  • O(1)：常数复杂度
  • O(log n)：对数复杂度
  • O(n)：线性时间复杂度
  • O(n^2)：平方
  • O(n^3)：立方
  • O(2^n)：指数
  • O(n!)：阶乘

注意：只看最高复杂度的运算，且不考虑系数
image.png

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

算法 递推公式 时间复杂度 备注
二分查找 T(n)=T(n/2)+O(1) O(logn) 一般发生在数列有序时
二叉树遍历 T(n)=2T(n/2)+O(1) O(n)
有序二维矩阵 T(n)=2T(n/2)+O(log n) O(n)
归并排序 T(n)=2T(n/2)+O(n) O(nlogn)

大O表示法

使用大O表示法衡量某个算法的复杂度，其实就是讲该算法的运行时间用输入量为n的函数表示出来，这里的n通常指代的就是算法操作的元素个数