Big O 基础介绍(一)

此文参考《程序员面试金典》(第六版)第六章

大O符号在算法中用于描述算法效率。

时间复杂度

时间复杂度(渐近运行时间)，也称为大O时间

举例：

假设有一个可以无限装下盒子的容器X，N个盒子，一个人P，地点A和B，从A到B运送时间相同。

方法一：P一次只能从A到B运送一个盒子

方法二：P也可以选择直接将盒子都装进X再从A到B运送容器X

使用方法一，随着盒子数目的增加，所消耗的时间也将线性增加，可以表示为O(N)

使用方法二，无论盒子怎么增加X都能装下，因此运送时间是固定的常量，可表示为O(1)

时间复杂度也能有很多的变量，比如给一个长X，宽Y，高Z的泳池注水，那么可以表示为O(XYZ)

O、θ 和Ω

学术界描述运行时间有三种，Big O、Big θ (theta) 和 Big Ω (omega)

  • Big O：用于描述运行时间的上界，假设一个算法可以描述为O(N)，那么也可以描述为O(N^2)。类似于，假设一个人可以活到130岁，那么年龄X<=130，也可以说年龄X<=1000，因为130是肯定小于1000的，这里的130就是上界。
  • Big Ω (omega)：用于描述运行时间的下界
  • Big θ (theta)：用于描述运行时间的确界，如果一个算法为 θ(N)，那么它既是O(N)，也是Ω(N)

在工业界中直接用O(N)表示确界。

空间复杂度

空间复杂度为算法占用的内存数量或者空间大小

如果要创建大小为N的数组那么需要的空间为O(N)。如果是n x n的数组，需要的空间为O(N^2)。

在递归里栈的空间也要算在内。下列sum函数运行时间为O(N)，空间也为O(N)。

1
2
3
4
5
6
int sum(int n){
    if(n <= 0){
        return 0;
    }
    return n + sum(n-1);
}

栈的调用过程如下

1
2
3
4
5
sum(4)
 ->sum(3)
   ->sum(2)
     ->sum(1)
       ->sum(0)

这里的递归调用都会添加到调用栈里并占用实际内存。

但是并不是n次调用都会占用O(N)的空间。

1
2
3
4
5
6
7
8
9
10
11
int pairSumSequence(int n){
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += pairSum(i, i + 1);
    }
    return sum;
}

int pairSum(int a, int b){
    return a + b;
}

pairSum方法调用n次，但是调用并不像递归那样同时发生，所以仅仅需要O(1)的空间。

删除常量

在特定时候O(N)可能比O(1)还快。例如下图

O(N)、O(1)比较, 取自《程序员面试金典》

时间复杂度描述的仅仅是算法时间的增长趋势，因此常量不计算在运行时间中。

例如O(2N)实际上是O(N)，不少人会认为代码中两个非嵌套的循环就是O(2N)这样描述更精确，其实并不。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int x : array){
    if (x < min) min = x;
    if (x > max) max = x;
}
#************************************
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(int x : array){
    if(x < min) min = x;
}
for(int x : array){
    if(x > max) max = x;
}

以上两段代码，第一段一个for循环，第二段两个for循环，但是第一个for循环里有两行，这个要怎么考虑呢？如果真的要详细计算时间复杂度，需要考虑汇编层次，乘法比加法多了多少指令，还要考虑编译器怎么优化等细节，太多太多了。这会让O的计算变得复杂。我们只需要知道一点，O(N)并不总是比O(N^2)快。

丢弃不重要的项

由O(2N)会舍弃常量变成O(N)可知，O(2N^2)会舍弃常量变成O(N^2)，那么O(N^2 + N)该怎么处理？

由O(2N^2)会舍弃常量变成O(N^2)可知，O(2N^2)可以表示为O(N^2 + N^2)，这里直接舍弃掉了一个N^2。因为 N < N^2 所以O(N^2 + N)也会变成O(N^2)。例子

特殊情况依旧存在，有的时候需要用和的形式表示运行时间。例如，O(B^2) + A 就已经是最简化的形式了。

下图是常见几个时间复杂度的增长速率。

增长速率