复杂度分析（上）笔记：如何分析、统计算法的执行效率和资源消耗

2018-12-20 本文已影响5人红酥手黄藤酒丶

复杂度分析（上）笔记：如何分析、统计算法的执行效率和资源消耗

一、关于对数阶时间复杂度的实例分析

求下列代码的时间复杂度：

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

解析：主要是看循环体的执行次数，也就是 i = i * 2 的执行次数，由于判断条件是 i <= n ，(①)则跳出循环前的最后一次执行后 i 等于 n，那么实际上变量 i 的取值就是一个 等比数列。

什么是等比数列？
等比数列是指从第二项起，每一项与它的前一项的比值等于同一个常数的一种数列。

上面代码中的每一个 i 与前一个 i 的比值都为 2，所以可以如下图表示：
约定 x 表示 i = i * 2 的执行次数，则有：

image

注：int i = 1 就相当于 2 的 0 次幂

所以有次数 x = ㏒(2)(n)(以 2 为底 n 的对数），所以时间复杂度就为 ○(㏒(2)(n))

对应的，下面代码的时间复杂度就为㏒(3)(n)：

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

教程中说根据对数的转换：log(3)(n) 就等于 log(3)(2) * log(2)(n)，对数的转换都忘了好久了，这里新学习一下：

image

在算法的世界中，常量因子是忽略不计的 log(3)(2) 就是一个常量，所以将其忽略。
这时候有意思的事情就来了，可以忽略 log(3)(2) 的话，是不是就说明在计算时间复杂度时，可以忽略底数了。

image

所以在对数阶时间复杂度的表示方法里，忽略对数的底，统一表示为： ○(logn)

如果一段代码的时间复杂度是 ○(logn) ，那么循环执行 n 遍，时间复杂度就是 ○(nlogn)，归并排序，快速排序的时间复杂度都是 ○(nlogn)（线性对数阶）。

二、不一样的时间复杂度：代码的复杂度由两个数据的规模决定

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

image

三、空间复杂度分析

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。
空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间和数据规模之间的增长关系。

简单示例：

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

image

总结

越高阶复杂度的算法，执行效率越低。
常见的复杂度并不多，从低阶到高阶有：○(1) ○(logn) ○(n) ○(nlogn) ○(n²)
所以执行效率由高到底：○(1) > ○(logn) > ○(n) > ○(nlogn) > ○(n²)

image

复杂度分析（上）笔记：如何分析、统计算法的执行效率和资源消耗