算法面试中的时间复杂度分析
算法面试中的时间复杂度分析
例子： 有一个字符串数组，首先将数组中每一个字符串按照字母序排序，之后再将整个字符串按照字典序排序。整个操作的时间复杂度？
答： 假设最长的字符串长度是s，数组中有n个字符串。
对每个字符串进行排序: slogs， 共有n个，所以 nslog(s)
所有的字符串进行排序：O(s*nlog(n)) //对字符串进行排序，每一次比较最多为s
==> O(n * slogs) + O(s * nlogn) = O(sn(logn + logs))
算法复杂度有些情况下是和用例相关的
对数据规模有一个概念 -- 封底估算
用下面的一个程序进行测试：
for(int x = 1; x <= 9; x++){
int n = pow(10, x);
clock_t startTime = clock();
int sum = 0;
for(int i = 0; i < n; i++)
sum += i;
clock_t endTime = clock();
cout << "10^" << x << " : "<< double(endTime - startTime)/CLOCKS_PER_SEC << " s"<< endl;
}
这是一个O(n)的算法在本机4核i7的机器跑出来结果如下：
10^1 : 0 s
10^2 : 0 s
10^3 : 0 s
10^4 : 0 s
10^5 : 0 s
10^6 : 0 s
10^7 : 0.03125 s
10^8 : 0.25 s
10^9 : 2.4375 s
也就是说，如果程序要求在1s内跑出结果，数据规模最好不要超过108,不要达到109，也就是说：
O(n^2): 大约可处理10^4级别的数据
O(n^logn): 大约可处理10^7级别数据
O(n): 大约可处理10^8级别数据
常见的复杂度分析
$O(1)$
void swap(int &a, int& b){
int tmp = a; a = b; b = tmp;
}
$O(n)$ --- 常系数很可能不为1
int sum(int n) {
int sum = 0;
for(int i = 1; i <= n; i++) {
sum += n;
}
return sum;
}
$O(n^{2})$
// 选择排序
for(int i = 0; i < n; i++){
int minIndex = i;
for(int j = i + 1; j < n; j++){
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
}
swap(arr[i], arr[minIndex]);
$O(logn)$
// lower_bound
int binSearch(const vector<int>& nums, int lo, int hi, int key) {
while(lo < hi) {
int mid = lo + (hi - lo) / 2;
if(nums[mid] < key) {
lo = mid;
}
else{
hi = mid;
}
}
return lo;
}
考虑下面这个例子：n经过几次除以10的操作后，等于0？ 答案是log_{10}n
// Warnning!! this code is buggy
// 需要考虑各种情况
string intToString (int num) {
string s = "";
while(num) {
s += '0' + num % 10;
num /= 10
}
reverse(s);
return s;
}
以2为底和以10为底的对数，在数量级上没有区别。（只是一个线性关系）
$O(nlogn)$
虽然下面的代码也是两重循环，但是复杂度却是$O(nlogn)$的，因为外层循环是指数级增加的（每次乘以2）
void hello(int n) {
for(int sz = 1; sz < n; sz += sz) {
for(int i = 1; i < n; i++){
cout << "Hello" << endl;
}
}
}
复杂度实验
我明明写的是$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) = 2f(n/2) + f(partition)$ 而partition操作只需要做一次循环，所以是一个O(n),所以
$$\begin{split}\f(n) &= 2f(n/2) + O(n)\&= 4f(n/4) + O(n) + 2O(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(2n)$, 那么这个视角下的均摊分析还是为级别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)$的级别
