数据结构与算法知否知否系列

algorithm

算法解决的是时间、空间上的问题，一般都会谈及复杂度概念，例如 Redis 的 incr 命令，我们都知道它是 O(1) 复杂度，算法就是时间、空间上的一个平衡艺术。

Q1: 快排算法复杂度是多少？

O(n2)

Q2: 常见复杂度有哪些？

  • O(1)：基本算法，加、减、乘、除等
  • O(logn)：二分查找
  • O(n^1/2)：n 的 1/2 次方求解，约数枚举
  • O(n)：线性查找
  • O(n^2)：朴素最近点
  • O(n^3)：Floyd 最短路、普通矩阵乘法
  • O(nlogn)：归并排序、快速排序的期望复杂度、基于比较排序的算法下界
  • O(2^n)：枚举全部子集数量

Reference