接着上一篇博文来讲一讲时间复杂度的具体计算方法。


算法时间复杂度的计算应该按照如下步骤:

  1. 找出算法中的基本语句
  2. 统计基本语句的执行次数得出$T(n)$。
  3. 对$ T(n) $进行渐进分析,并用恰当的符号表示。
    这里的基本语句可以理解为四则运算、比较运算等,可以根据实际情况灵活处理。

但实际上我们一般直接按照如下方法进行时间复杂度的分析:

  1. 找出基本语句中数量级最大的
  2. 统计以上基本语句的执行次数得出$ T(n) $。
  3. 对$ 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(清华大学出版社,严蔚敏)*/

这里偷个懒,直接把百度百科上的快排复制过来了。当然快速排序还有别的实现方法(如迭代法),这里至是拿它做个例子。

对于这类算法,一般分为三个步骤:

  1. 划分问题:把元素分为左右两个部分,使得左边的任意值小于右边的任意值。
  2. 递归求解:把左右两部分分别排序。
  3. 合并问题:这里不需要合并,因为最后数组已经是有序的了。

那么,假设划分问题的时间复杂度是$ Θ(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) $。


参考资料

  • 算法导论
  • 算法竞赛入门经典
Last modification:August 16, 2018
博客维护不易,如果你觉得我的文章有用,请随意赞赏