Big O 基础介绍(二)

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

多项式算法的加和乘

算法中常见的分步形式如下:

O( A + B ) :

for (int a : arrA){
    print(a);
}

for (int b : arrB){
    print(b);
}

O( A * B )：

for (int a : arrA){
    for (int b : arrB){
        print(a + "," + b);
    }
}

第一个例子，先遍历A数组，再遍历B数组，所以总数量是O( A + B )。

第二个例子，对A数组的每个元素都遍历B数组，所以总数量是O( A * B )。

在计算时间复杂度的时候常常会碰到最坏情况偶尔会出现，一旦发生会消耗很多资源，但是发生之后很长一段时间不会发生，因此需要兼顾正常情况和最坏情况，将时间进行”分摊“。

例如Java中ArrayList能够灵活的改变大小，能够随着你的插入进行扩容。

ArrayList容量达到限制的时候会创建一个双倍容量的数组，将元素复制到新的数组里面。

那么描述ArrayList的插入时间，当数组没有满的时候，插入就是O(1)。

当数组满了，如果数组大小为N，那么需要扩容到2N，并把旧的值复制过去，那么插入就需要O(N)。

那么”分摊时间“该怎么计算？

假设需要插入N个元素，ArrayList数组的大小为2的幂数，当插入一个元素便扩容两倍。当元素是N的时候，以1，2，4，8，16，32……，N的数组大小成倍的扩容。每次操作需要复制1，2，4，8，16，……，N个元素。

那么消耗便是1 + 2 + 4 + 8 + 16 + ··· + N的和，从右往左计算便是 N + N/2 + N/4 + N/8 + ··· + 1的和，这个和约等于2N。

因此，N次插入需要的时间便是O(2N)，即每次插入的分摊时间为O(1)。

以二分查找为例。如果一个排序数组的长度为N，目标值为x。首先比较x和中值的大小，如果等于就直接返回，如果x小于便搜索数组中值左边的部分，如果x大于中值便搜索右边的部分。

开始的时候有N个元素，搜索一次后便是N/2，接着是N/4，直到找到目标或者需要搜索的元素变成1。

假设有N个元素，总的运行时间便是从N到1一共搜索了多少次。

如果开始有32个元素

N = 32
N = 16 除以2
N = 8  除以2
N = 4  除以2
N = 2  除以2
N = 1  除以2

从32到1，需要5次

如果从1开始看，从1到32则需要2^5

因此得到2^k = N，k = log2(N)

所以得到运行时间O(logN)

平衡二叉搜索树中也有同样的情况，每次搜索便将规模减半，最坏情况为平衡二叉搜索树的高度，也是O(logN)。

int f(int n){
    if(n <= 1){
        return 1;
    }
    return f(n - 1) + f(n - 1)
}

通过模拟执行来显示运行时间，如果我们调用f(4)，那么会调用f(3)两次，每个f(3)又会调用f(2)两次，每个f(2)又会调用f(1)两次。如下图显示的节点展开。

图中一共展开了多少节点？

所以展开是2^0 + 2^1 + 2^2 + 2^3 = 2^4 -1

扩展到N则是2^0 + 2^1 + 2^2 + 2^3 + ··· + 2^N = 2^(N+1) - 1

因此时间复杂度为O(2^(N+1) - 1)舍弃掉常数项为O(2^N)

常见递归中复杂度通常为，O(分支数^递归深度)，偶尔也有特殊情况。