复杂度分析

淩亂°似流年 2023-06-16 10:51 16阅读 0赞

复杂度分析

（一）如何分析、统计算法的执行效率和资源消耗

1、大O复杂度表示法

算法的执行效率，粗略的讲，就是算法代码执行的时间。

所有代码执行的时间T(n)与每行代码的执行次数n成正比。

这个规律总结成一个公式就是大O了

T(n) = O(f(n)

这条公式里，Tn代表的是代码执行的时间，n代表的是数据规模的大小，fn表示每行代码执行的次数总和。公式中的O代表的是代码时间与fn表达式成正比。

下面来举个例子。

int cal(int n) {
    
       int sum = 0;
    
       int i = 1;
    
       for (; i <= n; ++i) {
    
         sum = sum + i;
    
       }
    
       return sum;
    
    }

这段代码中的执行时间预估一下，假设每行代码执行的时间一样，都为一个u的时间。

第1，2行都只执行了一次，而第3，4行都同时执行了n遍，所以这段代码总的执行时间为

(2n+2)\*u。也就是Tn = O(2n+2)

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

在上面例子中，当n很大的时候，常量2，系数2都可以忽略不记，我们只需要记录一个最大的量级就可以了。也就是可以记为Tn = O(n)

2、时间复杂度分析

（1）只关注循环次数最多的一段代码。这段核心代码执行次数的n的量级，就是整段要分析代码的时间复杂度。

比如上面的例子

int cal(int n) {
    
       int sum = 0;
    
       int i = 1;
    
       for (; i <= n; ++i) {
    
         sum = sum + i;
    
       }
    
       return sum;
    
    }

其中2、3行代码都是常量级的执行时间，与n的大小无关，所以对于复杂度并没有影响。循环执行次数最多的就是第4、5行代码，所以这块代码要重点分析。

（2）加法法则：总复杂度等于量级最大的那段代码的复杂度。

int cal(int n) {
    
       int sum_1 = 0; //1
    
       int p = 1;// 1
    
       for (; p < 100; ++p) { //100
    
         sum_1 = sum_1 + p;//100
    
       }
    
    
    
    
    
       int sum_2 = 0;//1
    
       int q = 1;//1
    
       for (; q < n; ++q) {//n
    
         sum_2 = sum_2 + q;//n
    
       }
    
       int sum_3 = 0;//1
    
       int i = 1;//1
    
       int j = 1;//1
    
       for (; i <= n; ++i) {//n
    
         j = 1;//n
    
         for (; j <= n; ++j) {//n2
    
           sum_3 = sum_3 +  i * j;//n2
    
         }
    
       }
    
       return sum_1 + sum_2 + sum_3;
    
    }

1+1+200+1+1+2n+1+1+1+2n+2n\*n

在这里，代码分为三个部分，分别是求sum1,sum2,sum3，可以分别分析每一部分的时间复杂度，然后再取一个量级最大的作为整段代码的复杂度。

综合这三段代码的时间复杂度，取其中最大的量级，所以整段代码复杂度就是O(n2)(2是平方)

所以抽象成公式为

T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

（3）乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).

3、集中常见的时间复杂度实例分析

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70][]

把时间复杂度为非多项式量级的算法问题叫做NP（非确定多项式）问题。当数据规模n越来越大的时候，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。（ O(2n) 和 O(n!)。）这里的n是2的指数

（1）O(1)

这里的O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。一般情况下，只要算法中不存在循环语句，递归语句，即使有成千上万行的代码，其时间复杂度都是O(1)

（2） O(logn)、O(nlogn)

我们来看下下面这段代码

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

这里的循环代码就只有第三行，所以我们只要计算出第三行的执行次数就能得到它的时间复杂度。

那么这里循环的关键在于n的大小

![20191126111754174.png][]

x就是我们的执行次数，那么现在已知n求x，就是我们的对数函数，x= log2n

所以这段代码的时间复杂度就是O(log2n)。

因为对数之间是可以进行相互转换的,log3n 就等于 log32 \* log2n，所以 O(log3n) = O(C \*  log2n)，其中 C=log32 是一个常量。基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n)),也就是说，在对数阶时间复杂度的表示方法中，底数是可以忽略不记的。所以就可以统一为O(logn)

如果这段代码是在一个循环里面的就变成了O(nlogn)了。常见的归并排序，快速排序的时间复杂度就是O(nlogn)

（3） O(m+n)、O(m\*n)

int cal(int m, int n) {
    
      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;
    
    }

这里的m、n是表示两个数据规模，无法事先评估谁比较大一点，所以这里就不能简单的省略掉其中一个。这里的复杂度就是O(m+n)

4、空间复杂度分析

空间复杂度就是算法的存储空间于数据规模之间的增长关系。

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]
    
      }
    
    }

在这里，我们一共用到了两个变量，其中i是常量阶的跟n没有关系，因此可以忽略，第3行申请了一个大小为n的int类型的数据，所以这里整段代码的空间复杂度就是O（n）。

因此空间复杂度就是看代码里面占用空间的大小。

5、小结

越高阶复杂度的算法，执行效率月底，常见的复杂度并不多，从低阶到高阶的有O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 1][]

（二）、复杂度分析

最好情况时间复杂度、最坏情况时间复杂度、平均情况时间复杂度、均摊时间复杂度

1、最好、最坏情况时间复杂度

最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。

最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度，

举个例子

// n表示数组array的长度

int find(int[] array, int n, int x) {
    
      int i = 0;
    
      int pos = -1;
    
      for (; i < n; ++i) {
    
        if (array[i] == x) {
    
           pos = i;
    
           break;
    
        }
    
      }
    
      return pos;
    
    }

在这段代码中，如果刚好第一个元素就是要查找的元素，那么时间复杂度就是O(1),而如果是最后一个元素是要查找的元素，那么时间复杂度就是O（n）。

2、平均情况时间复杂度

在上面的例子中，x在数组中的位置有n+1中情况（在数组的0~n-1位置中，或者不在数组中）。把每种情况下，查找需要遍历的次数统计起来再除以n+1，就可以得到平均值了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 2][]

但是，这里有个问题就是，这里的n+1中情况出现的概率并不是一样的，要知道，要查找的变量X，出现和不出现的概率都为1/2，此外，要查找的数据出现在各个位置的概率也是一样为1/n，所以要查找的数据出现在0~n-1中任意位置的概率为1/2\*1/n=1/2n

所以把各个情况发生的概率考虑进去，那么平均时间复杂度的计算过程就变成了：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 3][]

这个值就是概率论中的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度，也叫期望时间复杂度。

所以这里的平均时间复杂度，去掉常量和系数之后就是O（n）

3、均摊时间复杂度

每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

4、分析下面add函数的时间复杂度

// 全局变量，大小为10的数组array，长度len，下标i。
    
    int array[] = new int[10];
    
    int len = 10;
    
    int i = 0;
    
    // 往数组中添加一个元素
    
    void add(int element) {
    
       if (i >= len) { // 数组空间不够了
    
         // 重新申请一个2倍大小的数组空间
    
         int new_array[] = new int[len*2];
    
         // 把原来array数组中的数据依次copy到new_array
    
         for (int j = 0; j < len; ++j) {
    
           new_array[j] = array[j];
    
         }
    
         // new_array复制给array，array现在大小就是2倍len了
    
         array = new_array;
    
         len = 2 * len;
    
       }
    
       // 将element放到下标为i的位置，下标i加一
    
       array[i] = element;
    
       ++i;
    
    }

最好的时间复杂度就是o(1)，当i<=9时

最坏时间复杂度时O(n) ,当i==10

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191126111754440.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[20191126111754174.png]: https://img-blog.csdnimg.cn/20191126111754174.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191126111754227.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191126111754413.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191126111754435.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tyeXNsaWFuZw==,size_16,color_FFFFFF,t_70