时间复杂度

发表于 更新于 分类于
本文字数： 7.1k 阅读时长 ≈ 6 分钟

时间复杂度

第一节 概述

时间复杂度是一个函数，用于描述算法的运行时间。常用大O符号表示，如 O(n) 。时间复杂度可以被称为是渐进的，即考察输入值趋近于无穷时的情况，如一个算法对于任意数量n的输入，需要 5n^3^ + 3n 的时间运行完毕，则其渐进时间复杂度为 O(n^3^) 。

即使相同数目大小的不同输入值仍可能导致算法的运行时间不同，所以通常使用算法的最坏情况复杂度，即 T(n) 。

1.1 常见时间复杂度

  • O(n^3^)：矩阵乘法的基础实现。
  • O(n^2^)：冒泡排序、插入排序。
  • O(loglogn)：有界优先队列的单个操作。
  • O(nlogn)：最快的比较排序。
  • O(logn)：二分搜索。
  • O(n)：无序数组的搜索。
  • O(1)：奇偶判断。

对于时间复杂度中的对数表达式，一般默认底数为2（计算机偏爱2?），所以 logn 即 log2n。

第二节 计算时间复杂度

2.1 步骤

  1. 找出算法中的基本语句。
    • 基本语句即执行次数最多的语句，通常指最内层循环。
  2. 计算基本语句的执行次数的数量级。
    • 可忽略所有的低次幂和高次幂的系数。
  3. 用大O记号表示算法的时间性能。

2.2 实例

（1）单层和双层循环

1
2
3
4
5
for(int i = 0;i < n;i++)
       x++;
for(int i = 0;i < n;i++)
   	for(int j = 0;j < n;j++)
       	x++;

两种基本语句都是最内层循环 x++; 。

单层循环执行了 n 次，双层循环执行了 n^2^ 次。

所以二者的时间复杂度分别为 O(n) 和 O(N^2^) 。

（2）循环乘2

1
2
3
i = 1;
while(i <= n)
       i = i * 2;

基本语句 i = i * 2; ，设y为其执行次数，则 2^y^ <= n ，即 y <= log2n 。

所以 T(n) = O(log2n) 。

（3）冒泡排序

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                // 比较两个元素大小，若前大于后则交换
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}

基本语句即比较操作 arr[j] > arr[j + 1] ，其运行次数为 (n - 1) + (n - 2) + … + 2 + 1 = n (n - 1) / 2 = n^2^ / 2 。所以时间复杂度为 O(n^2^) 。

（4）选择排序

1
2
3
4
5
6
7
8
9
10
11
public static void sort(Comparable[] a){//将数组a按升序排序
    int N = a.length;//记录数组长度
    for(int i = 0;i < N;i++){//将a[i]与a[i+1...N]最小元素交换
        int min = i;
        //循环遍历找到当前最小元素
        for(int j = i+1;j < N;j++)
            if(less(a[j],a[min])) min = j;
        //将第i小元素交换至位置i
        exch(a,i,min);
    }
}

基本语句 min = j; ，其运行次数为 (n - 1) + (n - 2) + … + 2 + 1 = n (n - 1) / 2 = n^2^ / 2 。

所以时间复杂度为 O(n^2^) 。

（5）插入排序

1
2
3
4
5
6
7
8
9
public static void sort(Comparable[] a){
    int N = a.length;
    // 从第二个元素开始遍历数组
    for(int i = 1;i < N;i++){
    	// 第二层游标j从游标i开始，逆向遍历，不断和比其小的元素交换位置，直到移动到0位置
        for(int j = i;j > 0 && less(a[j],a[j-1]);j--)
            exch(a, j, j-1);
    }
}

基本语句 less(a[j],a[j-1]) ，其运行次数为 1 + 2 + … + (n - 2) + (n - 1) = n (n - 1) / 2 = n^2^ / 2 。

所以时间复杂度为 O(n^2^) 。

（6）希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void sort(Comparable[] a){
    int N = a.length;
    int H = 1;
    // 根据元素数目初始化H：1、4、13、40、121...
    while (H < N/3)
        H = 3*H + 1;
    //同插入排序，但游标不是相邻移动，而是间隔H，将a[i]插入到a[i-H],a[i-2H]...之中
    while (H >= 1) {
    	// 游标i从H开始遍历数组
        for(int i = H;i < N;i++){
        	// 游标j仍从游标i开始，逆向隔H遍历，
            for(int j = i; j >=H && less(a[j],a[j-H]);j-=H)//
                exch(a,j,j-H);
        }
        H = H/3;
    }
}

基本语句 less(a[j],a[j-H]) ，希尔排序的性能论证十分复杂，目前的结论是其运行时间达不到平方级别，运行次数本人目前浅陋的数学水平无法归纳，根据书本和互联网获得的答案是平均时间复杂度为 O(nlogn) ，最坏情况大概与 N^(3/2)^ 成正比，相比插入排序一点微小的改变就突破了平方的屏障，这正是算法设计的目标。

所以时间复杂度为 O(nlogn) 。

（7）归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Merge extends SortExample {
    public static void main(String[] args){
        Integer[] a = RandomUtil.getRandomIndex(10000);
        Stopwatch stopwatch = new Stopwatch();
        sort(a);
        System.out.println(stopwatch.elapseTime());
        show(a);
    }
    
    /**
     * 原地归并的抽象方法
     */
    public static void merge(Comparable[] a, int lo, int mid, int hi){
        //将a[lo,mid]与a[mid+1,hi]归并，两个数组是有序的
        int i = lo,j = mid+1;
        //先将所有元素复制到aux[]中，再归并到a[]中
        for(int k = lo;k <= hi;k++)
            aux[k] = a[k];
        //用i,j指针分别游离于两数组
        for(int k = lo;k <= hi;k++){
            if(i > mid) a[k] = aux[j++]; //左边下标已结束
            else if(j > hi) a[k] = aux[i++];//右边下标已结束
            else if(less(aux[j],aux[i])) a[k] = aux[j++];//两数组的指针比较当前大小，前者较小
            else a[k] = aux[i++];
        }
    }
    
    /**
     * 自顶向下的归并排序
     */
    private static Comparable[] aux; //归并所需的辅助数组

    public static void sort(Comparable[] a){
        aux = new Comparable[a.length];//一次性分配空间
        sort(a,0,a.length-1);
    }

    //将数组a排序，递归排序，sort的作用为以正确的顺序调用merge方法
    private static void sort(Comparable[] a,int lo,int hi){
        if(hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        sort(a,lo,mid);      // 将左半边排序
        sort(a,mid+1,hi);    // 将右半边排序
        merge(a,lo,mid,hi);  // 归并结果
    }
    
    /**
     * 自底向上的归并排序
     */
    public static void sortBottomUp(Comparable[] a){
        // 进行lgN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for(int sz = 1; sz < N ;sz = sz + sz) //sz-子数组大小
            for(int lo = 0; lo < N-sz;lo+=sz+sz) //子数组索引
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
    }
}

对于长度为N的任意数组，自顶向下的归并排序需要 1/2NlgN 至 NlgN 次比较，并且最多需要访问数组 6NlgN 次。

归并排序所需时间与 NlgN 成正比，这相比前几个排序要快很多（指数级），只需要比遍历整个数组多个对数因子的时间就可以将一个庞大的数组排序。

对于长度为N的任意数组，自底向上的归并排序需要 1/2NlgN 至 NlgN 次比较，最多访问数组 6NlgN 次。

所以时间复杂度为 O(nlogn) 。

（8）快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Quick {
	public static void sort(Comparable[] a){
        //消除对输入的依赖，需要在这里把元素随机分布一下
        StdRandom.shuffle(a);
        sort(a,0,a.length-1);
    }

    /**
     * 递归排序
     */
    public static void sort(Comparable[] a,int lo,int hi){
        //当左右游标相等，表示已对最小数组排序，结束递归
        if(hi <= lo) return;
        //切分
        int j = partition(a,lo,hi);
        //将左半部分排序
        sort(a,lo,j-1);
        //将右半部分排序
        sort(a,j+1,hi);
    }

    /**
     * 切分数组
     */
    private static int partition(Comparable[] a,int lo,int hi){
        //左右扫描指针
        int i = lo,j = hi + 1; 
        //切分元素
        Comparable v = a[lo];  
        //扫描左右，检查扫描是否结束并交换元素，遍历结束后数组被切分为两部分，一边小于切分元素，一边大于切分元素
        while(true){
            //循环遍历直到找到大于v元素或游标到底
            while(less(a[++i],v))
                if(i == hi) break;
            //循环遍历直到找到小于v元素或游标到头
            while(less(v,a[--j]))
                if(j == lo) break;
            //若游标交叉则表示以遍历所有元素，结束
            if(i >= j) break;
            //交换两边元素
            exch(a,i,j);
        }
        //将v=a[j]放入正确位置
        exch(a,lo,j); 
        //a[lo...j-1] <= a[j] <= a[j+1...hi] 达成
        return j;    
    }
}

所以时间复杂度为 O(nlogn) 。

T(n) = O(n^2^)

命题：将长度为N的无重复元素数组排序，快速排序平均需要 ~ 2NlnN 次比较，以及 1/6 的交换。

证明：CN 为将N个不同元素排序平均所需的比较次数。很明显 C0 = C1 = 0，对于 N > 1 ，由递归程序可以得到以下归纳关系：

CN = N + 1 + (C0 + C1 + … + C(N-2) + C(N-1)) / N + (C(N-1) + C(N-2) + … + C0) / N

第一项是切分的成本（总是N+1），第二项是将左子数组排序的平均成本，第三项是将右子数组（长度和左子数组相同）排序的平均成本。将等式左右两边乘以N并整理各项得到：

NCN = N (N + 1) + 2(C0 + C1 + … + C(N-2) + C(N-1))

将该等式减去 N - 1 时的相同等式可得：

NCN - (N - 1)C(N - 1) = 2N + 2C(N - 1)

整理等式并将两边除以 N(N + 1) 可得：

CN / (N + 1) = C(N - 1) / N + 2 / (N + 1)

归纳法推导可得：

CN ~ 2(N + 1)(1/3 + 1/4 + … + 1 / (N + 1))

括号内的量是曲线 2 / x 下从3到N的离散近似面积加一，积分得到 CN ~ 2NlnN 。注意 2NlnN ≈ 1.39NlgN ，也就是说平均比较次数只比最好情况多39%。

命题：快速排序最多需要 N^2/2 次比较，但随机打乱数组能够预防这种情况。

证明：在每次切分后两个子数组之一总是空的情况下，比较次数为：

N + (N - 1) + … + (N - 2) + 2 + 1 = (N + 1) N / 2

这说明了算法所需时间为平方级别，所需空间是线性的，而这对于大数组来说是不可接受的。比较次数的标准差为0.65N，因此随着N的增大，运行时间会趋于平均数，且不可能与平均数偏差太大。

（9）堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 堆排序
 */
public class Set extends SortExample {
    
    public static Comparable[] sort(Comparable[] c){
        Comparable[] a = new Comparable[c.length+1];
        int N = c.length;
        for (int i = 0;i < N;i++)
            a[i+1] = c[i];
        // for循环构造堆，sink方法将a从1到N排序
        for(int k = N/2; k >= 1; k--)
            sink(a,k,N);
        show(a);
        // while循环将最大元素a[1]和a[N]交换，并修复堆
        while (N > 1){
            exch(a,1,N--);
            sink(a,1,N);
            show(a);
        }
        return a;
    }

    private static void swim(Comparable[] a,int k){
        while (k > 1 && less(k/2,k)){//循环判断条件，k>1,父结点的值比当前小
            //交换当前结点和父结点的值，以及当前游标所指下标
            exch(a,k/2,k);
            k = k/2;
        }
    }

    private static void sink(Comparable[] a,int k,int N){
        while (2*k <= N){//循环判断条件，当前游标所指有子结点存在
            int j = 2*k;
            //当子结点不是最后结点，且子结点小于右子结点，指较大的那个子结点
            if(j < N && less(a[j],a[j+1]))
                j++;
            //如果当前结点比子结点大就跳出循环
            if(!less(a[k],a[j]))
                break;
            //交换，更新游标
            exch(a,k,j);
            k = j;
        }
    }

    public static void exch(Comparable[] a,int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args){
        // Integer[] a = RandomUtil.getRandomIndex(10000);
        Comparable[] a = {'S','O','R','T','E','X','A','M','P','L','E'};
        Stopwatch stopwatch = new Stopwatch();
        a = sort(a);
        System.out.println(stopwatch.elapseTime());
        show(a);
    }
}

将N个元素排序，堆排序只需要少于 2NlgN + 2N 次比较，以及一半次数的交换。

所以时间复杂度为 O(nlogn) 。

参考：

🔗 时间复杂度- 维基百科

🔗 如何理解算法时间复杂度的表示法，例如 O(n²)、O(n)、O(1)、O(nlogn) 等