Skip to main content

大 O 复杂度表示法

为什么需要复杂度分析​

通过计算一个算法执行的时间和占用的内存大小并不准确: 比如 i9 CPU 跑的程序 i3 CPU 跑的程序时间一定是不同的; 再如对于小规模的数据排序, 插入排序可能反倒会比快速排序要快. 因此这种方法的测试结果非常依赖测试环境, 并且测试结果受数据规模的影响很大.

时间复杂度​

时间复杂度是对一个算法运行时间长短的度量, 常见的时间复杂度有 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn).

空间复杂度​

空间复杂度是一个算法运行过程中临时占用存储空间大小的度量, 它包含下面几种:

  • 一维空间: 如一个字符串变量, 空间复杂度为 O(1)
  • 线性空间: 如一个一维数组, 空间复杂度为 O(n)
  • 二维空间: 如一个二维数组, 空间复杂度为 O(n2)
  • 递归空间: 对于递归, 在计算机运行程序时, 会专门分配一块内存, 用来存储“方法调用栈”, “方法调用栈” 包含进栈和出栈两个行为.

最好情况时间复杂度​

最好情况时间复杂度就是, 在最理想的情况下, 执行这段代码的时间复杂度.

最坏情况时间复杂度​

最坏情况时间复杂度就是, 在最糟糕的情况下, 执行这段代码的时间复杂度.