算法面试中的时间复杂度分析

复杂度实验

我明明写的是\(O(nlogn)\)的算法，面试官却说我是\(O(n^{2})\)的？

可以自己进行验证，看能够处理什么级别的数据规模，参考封底估算。
实验，观察趋势。比如每次将数据规模提高两倍，观察时间变化.

递归算法的复杂度分析

对于单次递归调用，复杂度一般为\(O(T*depth)\), 写递推表达式进行推导。

如下面的代码：

double pow(double x, int n) {
    assert(n >= 0);
    if(n == 0) return 1;
    
    double t = pow(x, n/ 2);
    if(n %2) 
        return x*t*t;
    else
        return t*t;
}

递归深度\(depth = logn, T = 1\),因此复杂度为\(O(logn)\)。

int f() {
    //递归基 here
    return f(n - 1) + f(n - 1);
}

多次递归调用,递归深度\(depth = n, 每次操作2\)，可以推导出算法复杂度为指数级\(O(2^n)\)
\[\begin{equation}\begin{split}\\f(n) &= 2f(n-1)\\&= 4(n-2)\\&= 8f(n-3)\\&\cdots\\&= 2^{n}f(1)\\&= O(2^{n})\\\end{split}\end{equation} \tag{1}\]

简单不严谨地分析快速排序的复杂度：

快速排序的每一次partition操作可构造出这么一个位置，即左边的所有值都比轴点小，右边的都比轴点大，因此\(f(n) = 2*f(n/2) + f(partition)\) 而partition操作只需要做一次循环，所以是一个O(n),所以
\[\begin{split}\\f(n) &= 2f(n/2) + O(n)\\&= 4f(n/4) + O(n) + 2*O(n/2)\\&= 8f(n/8) + O(n) + 2*(n/2) + 4*(n/4)\\&\cdots\\&= 2^{\log_{2}n} * f(1) + \underbrace{ O(n) + O(n) +\cdots+ O(n) }_{k = \log_{2}n个}\\&= n + O(n*\log_{2}n)\\&= O(n * \log_{2}n)\\\end{split} \tag{2}\]
当然，严谨的分析还需要引入概率（随机分布）。这里只是简单不严谨的推导。

均摊复杂度分析 Amoritzed Time

典型例子：动态数组(vector)
每一次动态扩容(resize())，需要开辟一个新的空间，然后进行一一赋值，这样一个操作的复杂度是\(O(n)\)那么问题来了：vector push_back的平均复杂度是多少？

假设当前数组容量为n,从空到满，每一次操作的消耗是\(O(1)​\). 如果此时再来一个元素，就需要resize, 那么最后这一次操作耗费为\(O(n)​\), 那么平均来看，过去n+1次操作的总花费为
\[ \underbrace{ O(1) + O(1) +\cdots+ O(1) }_{n个} + O(n) = O(2n)\]
那么分摊来看每一次push_back的操作花费为\(O(\frac{2n}{n+1}) = O(2) = O(1)\)

那么问题又来了，如果pop_back的时候，发现size为当前capacity的1/2就resize,那么时间复杂度是多少？
假设当前数组容量为2n,从满到一半，每一次操作的消耗是\(O(1)\),如果此时再pop_back,需要再消耗的时间为\(O(2*n)\), 那么这个视角下的均摊分析还是为级别O(1)
可是换一种奇怪的情况：数组满后，resize为两倍,需要O(n)；此时又要删除，那么又到达临界点了，此时要resize缩容，又需要\(O(n)\),那么在这种退化情况下，单次操作复杂度退化到了\(O(n)\), 这种情况也被称之为复杂度的振荡

正确的做法是什么呢？pop_back要等到size为capacity的1/4再resize缩容。

面试被问过的复杂度分析

假设现在的动态数组/哈希表有n个元素，vector的初始大小为1，问从开始到现在，共有多少次复制操作？

最后一次复制：n/2参与

倒数第二次复制：n/4参与

倒数第三次复制：n/8参与

...

第二次：2个参与

第一次：1个参与

\[\therefore S(n) = \frac{n}{2} + \frac{n}{4} + \frac{n}{8} +\cdots+4+2+1 \tag{3}\]

\[\Rightarrow 2S(n) = n + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} +\cdots+4+2 \tag{4}\]

很容易就可以得出

\[S(n) = n - 1 \tag{*}\]

也就是说，每一次插入新元素的复杂度能够分摊为\(O(1)\)的级别