By welkin

Updated:

Contents
  1. 1. 一、复杂度是什么？
  2. 2. 二、为什么需要复杂度分析？
  3. 3. 三、如何表示
  4. 4. 四、时间复杂度分析
    1. 4.0.1. 几种常见的时间复杂度实例分析
      1. 4.0.1.1. 1. O(1)
      2. 4.0.1.2. 2. O(logn)、O(nlogn)
      3. 4.0.1.3. 3. O(m+n)、O(m*n)
  • 5. 五、空间复杂度
  • 6. 六、浅析最好、最坏、平均、均摊时间复杂度
    1. 6.0.1. 1. 最好、最坏时间复杂度
    2. 6.0.2. 2.平均时间复杂度
    3. 6.0.3. 3. 均摊时间复杂度

    • 最近在看王争的数据结构与算法之美，里面有讲到数据结构中的复杂度分析，于是做个总结。

    一、复杂度是什么？

    复杂度分为时间、空间复杂度，是考量代码执行效率的一个重要指标

    二、为什么需要复杂度分析？

    在书中，老师给了两个原因，如下：做分别解释：

    1. 测试结果非常依赖测试环境
      比如同样的代码在不同的处理机上执行的速度不一样

    2. 测试结果受数据规模的影响很大
      对于测试较小的规模，执行时间的差别很大。

      三、如何表示

      大O复杂度表示法
      所有代码执行时间T(n)与每行代码的执行次数n成正比
      即：T(n) = O f(n)
      举例：

      1
      2
      3
      4
      5
      6
      7
      8
       int cal (int n){
      	int sum = 0;
      	int i = 1;
      	for(; i<=n; i++){
      		sum = sum + i;
      	}
      	return sum;
      }

    这个代码第2、3行分别需要1个unit_time的执行时间，4、5行都运行了n遍，所以需要2n*unit_time的执行时间，所以这段代码的执行时间就是(2n+2)unit_time。

    可以看出，所有代码的执行时间T(n)与每行代码的执行次数n成正比
    T(n) = O( 2n+2 )

    大O复杂度实际上并不具体代表代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度，简称时间复杂度。

    当n很大时，公式中的低阶、常量、系数不会左右增长趋势，所以都可以忽略。只需用记录一个最大量级就可以了，所以上段代码就可以表示为 T(n) = O(n)。

    四、时间复杂度分析

    1. 只关注循环执行次数最多的一段代码
    2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
    3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

      几种常见的时间复杂度实例分析

      1. O(1)

      O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。
      只要代码的执行时间不随n的增大而增大，这样的代码时间复杂的都为O(1)。
      一般情况下，只要不出现循环、递归，成千上万的代码，其时间复杂度也都是O(1)

      2. O(logn)、O(nlogn)

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

    时间复杂度为O(log2n)

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

    同理，时间复杂为O(log3n)
    实际上不管是以2还是3为底，我们都把对数阶的时间复杂度都记为O(logn)

    同理，对于O(nlogn)，我们循环执行n遍，时间复杂度就是O(nlogn)了

    3. O(m+n)、O(m*n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14

    int cal(int m, intn) {
    	int sum_ 1 = 0;
    	int i= 1;
    	for(;i< m; ++i){
    		sum_ _1=sum_ 1 + i;
    	}
    	int sum_ 2=0;
    	int j= 1;
    	for(;j<n;++j) {
    		sum_ 2=sum_ 2 + j;
    	}
    	return sum_ 1 + sum_ _2;
    }

    这段代码的时间复杂度就是 O(m+n)
    换成乘法，时间复杂度就是O(m*n)

    五、空间复杂度

    空间复杂度全称渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
    我们常见的空间复杂度就是0(1)、0(n)、0(n*n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11

    void print(int n) {
    	int i= 0;
    	int[] a = new int[n];
    	for (i;i<n; ++i) {
    		a[i]=i*i;
    	}
    	for(i=n-1;i>=0;--i){
    		print out a[i]
    	}
    }

    在这段代码中，第3行申请了一个大小为n的int类型数组，除此之外，剩下的代码没有占用更多的空间，所以整段代码的时间复杂度就是0(n)。

    六、浅析最好、最坏、平均、均摊时间复杂度

    1. 最好、最坏时间复杂度

    假如在一个无序数组中，需要查找一个数字，如果这个数字在最后面，那么这段代码的时间复杂度就是0(n)，
    同理，这个数字要是在首位，则就是0(1)
    因此，最好时间复杂度就是在最理想的情况下，查找的变量x是数组的第一个元素
    同理，最坏时间复杂度就是在最糟糕的情况下，执行这段代码的时间复杂度

    2.平均时间复杂度

    对于平均时间复杂度
    比如，元素x在数组有n+1种情况，就是把每种情况下需要遍历的元素个数累加起来，然后再除以n+1，就可以得到需要遍历的元素的个数的平均值

    3. 均摊时间复杂度

    就是将耗时多的操作均摊到耗时少的操作上。
    比如在数组中插入数据，每一次O(n)的插入操作，都会跟着n-1次0(1)的插入操作，所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是0(1)。这就是均摊分析的大致思路。

    这些大致是我的个人总结，如果还是看不太懂，最好是读原著加以理解