【算法与数据结构】复杂度分析

       本文记录了博主对算法复杂度分析，常见的几种复杂度，以及平均时间复杂度、最好/最坏时间复杂度的总结。

复杂度分析

　　关于算法的复杂度，我们通常采用大O来进行表示，在此我们假设每行代码的执行时间都一样，为一个单位时间，然后在这个假设的基础上进行时间、空间复杂度的分析。先分析一下上面的代码，2-4行的时间复杂度为3，紧接着有两个for循环，第一个for循环的时间复杂度为n，同时第6行的时间复杂度也为n，而内部的for循环的时间复杂度为2*n*n。总的时间复杂度则为2*n*n + 2*n+3。因此，此算法的时间复杂度为O(2*n*n + 2*n+3)。在此关于复杂度分析，有三点需要注意的：

　　1、总的时间复杂度等于量级最大的那端代码的复杂度，分析算法的时间复杂度的时候，常常忽略常数阶，低阶， 系数。因此分析一个算法的时间复杂度的时候，我们只需要关注量级最大的那段即可。

2、乘法规则： 嵌套的代码等于嵌套代码体内外执行时间的乘积。我们可以发现在for循环的嵌套中，基本都采用了这个规则。 如下面这段代码，外部for循环的复杂度为O(3*n), 第2个for循环的复杂度则为O(2*n)， 整个代码的时间复杂度为O(2*n)*O(n) + O(2*n) + 3；因此改代码的复杂度为O(n*n)

             1
            int cal(int n) {
 2int sum = 0;
 3int i = 1;
 4int j = 1;
 5for (; i <= n; ++i) {
 6      j = 1;
 7for (; j <= n; ++j) {
 8        sum = sum +  i * j;
 9     }
10   }
11  }

常见的几种复杂度

常见的时间复杂度有如下：主要分为两类，多项式两级和非多项式量级，其中非项式量级主要有两个：指数阶和阶乘阶。具有这种量级复杂度的问题也被成为NP难问题。

　　 常量阶o(1)

            int a = 0;
int b = a;
int i;

　　对数阶O(logn)

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

　　2的x次方 = n 可以得出 x = log2 n 因为在采用O标记表示时间复杂度的时候忽略系数，所以本段代码的时间复杂度为O(log n) ; 需要注意的是如果将第3行的 2 换成3， 时间复杂度依旧为O(log n), 由于对数的运算规则不同的底之间是可以相互转换的，log3n = log32 * log2n

　　线性对数阶O(nlogn)

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

　　O(m+n)

             1
            int cal(int m, int n) {
 2int sum_1 = 0;
 3int i = 1;
 4for (; i < m; ++i) {
 5     sum_1 = sum_1 + i;
 6  }
 7int sum_2 = 0;
 8int j = 1;
 9for (; j < n; ++j) {
10     sum_2 = sum_2 + j;
11  }
12return sum_1 + sum_2;
13 }

　　O(m*n)

            1
            int cal(int m, int n){
2int sum_2 = 0;
3int j = 1, i = 1;
4for (; j < n; ++j) {
5for(; i<m; ++i)
6       sum_2 = sum_2 + j;
7   }

三、最好/最坏、平均时间复杂度

            1
            //
             n表示数组array的长度
            2
            int find(int[] array, int n, int x) {
3int i = 0;
4int pos = -1;
5for (; i < n; ++i) {
6if (array[i] == x) pos = i;
7  }
8return pos;
9 }　

　　最好时间复杂度

　　最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。以上述代码为例，该代码为find函数，查找某个数字在数组重点位置，最理想的情况就是我们查找的数字位数数组的第一个位置，时间复杂度为O(1)。

　　最坏时间复杂度

　　最坏时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。还是以上述代码为例，最坏的情况就是，我们要查找到数不在数组中，需要遍历整个数组，这个时候算法的时间复杂度为O(n)。

　　平均时间复杂度

　　平均时间复杂度就是考虑算法的每种情况下，将每种情况的执行时间累加起来，然后再除以所有可能发生的情况数，就可以得到需要遍历的元素个数的平均值。分析上面这个代码的平均时间复杂度，一共有n+1种情况（0~n-1找到或n未找到）我们可以发现该算法的平均时间复杂度为(1+2+……+n+n)/n+1 = n(n+3)/[2(n+1)] ，我们可以得到，平均复杂度为O(n)。

　　类似平均时间复杂度还有加权平均时间，将每个情况发生的概率统计进来。也就是概率论中的加权平均值，上面每种情况发生的概率为1/(1+n)，在平均时间复杂度的基础上乘以1/(1+n)，得到加权平均时间复杂度O(1)。

原文：https://www.cnblogs.com/Trevo/p/11983888.html