菜鸟笔记
提升您的技术认知

数据结构与算法 算法的复杂度

阅读 : 62

算法的复杂度

大O复杂度表示法

 公式:

T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式, 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

      所以,第一个例子中的T(n) = O(2n+2),第二个例子中的T(m) = 0(2n2 +2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

      当n很大时,你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了,如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。
 

复杂度分析法则

1)单段代码看高频:比如循环。
2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。
3)嵌套代码求乘积:比如递归、多重循环等
4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

时间复杂度分析

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

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

多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括,
O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)
非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括,
O(2^n)(指数阶)、O(n!)(阶乘阶)

  • O(1) :

常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长,这样代码的时间复杂度我们都记作 O(1)。

  • O(logn)、O(nlogn)
i=1;
while(i<=n) {
    i = i*2;
}

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

  • 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是表示两个数据规模。我们无法事先评估m和n谁的量级大,所以我们在表示复杂度的时候,就不能简单地利用加法法则,省略掉其中一个。所以,上面代码的时间复 杂度就是0(m+n)。

针对这种情况,原来的加法法则就不正确了,我们需要将加法规则改为: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法则继续有效: T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系。

void print(int n) {
    inti=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]
    }
}

跟时间复杂度分析一样,我们可以看到,第2行代码中,我们申请了一个空间存储变量i,但是它是常最阶的,跟数据规模n没有关系,所以我们可以忽略。第3行申请了一个大小为n的int类型数组,除此之外,剩下的代码都没有占用更多的空间,所以整段代码的空间复杂度就是O(n)。

我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且,空间复杂度分析比时间复杂度分析要简单很多。所以,对于空间复杂度,掌握刚我说的这些内容已经足够了。

复杂度增长趋势图:

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

一、复杂度分析的4个概念
1.最坏情况时间复杂度:代码在最坏情况下执行的时间复杂度。
2.最好情况时间复杂度:代码在最理想情况下执行的时间复杂度。
3.平均时间复杂度:代码在所有情况下执行的次数的加权平均值。
4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

二、为什么要引入这4个概念?
1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

三、如何分析平均、均摊时间复杂度?
1.平均时间复杂度
代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。
2.均摊时间复杂度
两个条件满足时使用:

1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;

2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。