接着上一篇博文来讲一讲时间复杂度的具体计算方法。
算法时间复杂度的计算应该按照如下步骤:
- 找出算法中的基本语句。
- 统计基本语句的执行次数得出$T(n)$。
- 对$ T(n) $进行渐进分析,并用恰当的符号表示。
这里的基本语句可以理解为四则运算、比较运算等,可以根据实际情况灵活处理。
但实际上我们一般直接按照如下方法进行时间复杂度的分析:
- 找出基本语句中数量级最大的。
- 统计以上基本语句的执行次数得出$ T(n) $。
- 对$ T(n) $进行渐进分析,并用恰当的符号表示。
举个具体的例子:
int tot = 0;
for(int i=0;i<n;i++)
for(int j=0;i<j;i++)
tot++;
for(int i=0;i<n;i++)
temp[i] = 1;
拿上面的代码分析如下:
int tot = 0; //基本语句 执行一次
for(int i=0;i<n;i++)
for(int j=0;i<j;i++)
tot++; //基本语句 执行n^2次
for(int i=0;i<n;i++)
temp[i] = 1; //基本语句 执行n次
有人在分析的时候会把for循环中的循环变量赋值语句当作基本语句也算在内,但实际上这是完完全全没有必要的,原因请继续看下面的分析:
找出基本语句并得出其执行次数后,我们得到这段算法的时间复杂度$ T(n)=n^2+n+1 $。
对其进行渐进分析,舍去常数和低次项,得到$ T(n)=O(n^2) $。
这里可以精确的记作$ T(n)=Θ(n^2) $这也是所谓的用恰当的符号表示(一般用大$ O $)。
但是如上的分析方法太过啰嗦,因为我们都知道,在数据量达到一定规模的时候,$ f(n)=n^2 $的增长率将远远大于$ f(n)=n $。
所以我们直接找到数量级最大的那个循环嵌套语句,得到$ T(n)=O(n^2) $。
到这里,我们可以知道为什么没必要把循环变量赋值语句当作基本语句了——因为在最后的渐进分析中它总会被作为常数项忽视。
当然,这种方法在分析有用到分治等思想的算法的时候会遇到困难,我们在下面用快速排序做例子继续讨论:
#include <iostream>
using namespace std;
void Qsort(int a[], int low, int high) {
if(low >= high) {
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一个记录作为枢轴*/
while(first < last) {
while(first < last && a[last] >= key) {
--last;
}
a[first] = a[last];/*将比第一个小的移到低端*/
while(first < last && a[first] <= key) {
++first;
}
a[last] = a[first];
/*将比第一个大的移到高端*/
}
a[first] = key;/*枢轴记录到位*/
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
int main() {
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
cout << a[i] << "";
}
return 0;
}/*参考数据结构p274(清华大学出版社,严蔚敏)*/
这里偷个懒,直接把百度百科上的快排复制过来了。当然快速排序还有别的实现方法(如迭代法),这里至是拿它做个例子。
对于这类算法,一般分为三个步骤:
- 划分问题:把元素分为左右两个部分,使得左边的任意值小于右边的任意值。
- 递归求解:把左右两部分分别排序。
- 合并问题:这里不需要合并,因为最后数组已经是有序的了。
那么,假设划分问题的时间复杂度是$ Θ(n) $,那么我们可以知道$ T(0)=Θ(1) $。如果每一次对问题的划分都是考虑极端情况的话(也就是退化为插入排序的情况)可以得到递推表达式$ T(n)=T(n-1)+T(0)+Θ(n)=T(n-1)+Θ(n) $,解为$ T(n)=Θ(n^2) $。(这里我用的是代入法求的,不在这里讨论)
当然,这是一种极端坏的情况,不如我们来讨论一下极端好的情况,这时候可以得出递归式为$ T(n)=2T(n/2)+Θ(n) $,也就是平衡划分子问题(这里忽略了一些余项及减1操作的影响),根据主定理(https://zh.wikipedia.org/zh-hans/%E4%B8%BB%E5%AE%9A%E7%90%86)可以得到$ T(n)=Θ(n\log{n}) $。
所以我们说快速排序不稳定,在最坏的情况下会退化为$ O(n^2) $。
参考资料
- 算法导论
- 算法竞赛入门经典