【数据结构&算法】02-复杂度分析之执行效率和资源消耗

目录

• 前言
• 复杂度
• 分析方法
  • 大 O 复杂度表示法
    • 例子-评估累加和的各种算法执行效率
      • 算法 1（for 循环）：
      • 算法 2（嵌套 for 循环）：
    • 大 O 表示
  • 时间复杂度分析
    • 关注执行最多的一段代码
    • 加法规则
    • 乘法规则
• 常见时间复杂度
  • 常量阶 O(1)
  • 对数阶 O(logn)、O(nlogn)
  • 多参数阶 O(m+n)、O(m*n)
• 空间复杂度分析
• 小结

前言

本笔记主要记录如何分析、统计算法的执行效率和资源消耗。

必须学会分析复杂度分析。

李柱明博客：https://www.cnblogs.com/lizhuming/p/15487271.html

复杂度

复杂度分为：

1. 时间复杂度。关联到执行效率。

   • 时间复杂度的全称是 渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

2. 空间复杂度。关联到资源消耗。

   • 空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

分析方法

大 O 复杂度表示法

先说结论：

• 大 O 复杂度表示方法只是表示一种变化趋势。
• 忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。
• 多、加法和乘法规则。

例子-评估累加和的各种算法执行效率

算法 1（for 循环）：

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

• 从 CPU 角度看：

  • 重复类似的操作：读数据-运算-写数据。
  • 假设每行代码执行事件都为 unit_time。（粗略估计）
  • 代码中执行的时间为：T(n) = (2+3n)*unit_time。

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

算法 2（嵌套 for 循环）：

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

• 代码中执行时间为：T(n) = (3+3n+3n²)*unit_time=3(n²+n+1)*unit_time。
• 所有代码的执行时间 T(n) 与每行代码执行的次数成正比。

大 O 表示

T(n) = O(f(n))

• 上面算法 1 中的大 O 表示法为：T(n) = O(2+3n)。

• 上面算法 2 中的大 O 表示法为：T(n) = O(3(n²+n+1))。

• 大 O 表示法不是表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。

  • 即是时间复杂度。

当 n 很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。

只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，可记为：

• T(n) = O(n)；
• T(n) = O(n²)。

时间复杂度分析

当了解了大 O 表示法后，就可以用来分析时间复杂度了。

三个实用的方法：

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

关注执行最多的一段代码

以上面算法 1 为例：

• 前面两行代码为常量级别，忽略。

• 3n 中的系数也可忽略。

• 结论：时间复杂度为 O(n)

算法 2 的时间复杂度就是 O(n²)

加法规则

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

• 公式：T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))。

若上面算法 1 和算法 2 出现在同一个代码段中是，其时间复杂度之和为 O(n)+O(n²)。

总的时间复杂度就是取最大量级： O(n²)。

乘法规则

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

• 公式：T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))。

例子：

• 时间复杂度：T(n) = T1(n) * T2(n) = O(n*n) = O(n²)。

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

int cal(int n)
{
  int ret = 0; 
  int i = 1;
  for (; i < n; ++i) 
  {
    ret = ret + func(i);
  } 
} 

常见时间复杂度

常见时间复杂度量级如图：

这些复杂度量级可分为：

• 多项式量级：

  • 常量阶：O(1)
  • 对数阶：O(logn)
  • 线性阶：O(n)
  • 线性对数阶：O(nlogn)
  • k 次方阶：O(nk)（注意：这里的 k 为 k 次方)

• 非多项式量级

  • O(2ⁿ);（注意：这里的 n 为 n 次方)
  • O(n!)。
  • 说明：当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

常量阶 O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。

大牛总结：（常量级记作 O(1)）

• 只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。
• 或者说， 一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 Ο(1) 。

对数阶 O(logn)、O(nlogn)

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

时间复杂度分析过程：

• 多：第 4 行代码执行次数最多。那就算出第四行执行的次数。

• 

• 得 x = log₂n 即时间复杂度为 O(log₂n)。也就是 O(logn)。

• 不管底数为何值，都把这类对数阶的时间复杂度记为 O(logn)。理由：

  • log₃n = log₃2 * log₂n。对应时间复杂度为：O(log₃n) = O(C * log₂n)。
  • 按前面学的系数可忽略：O(log₃n) = O(log₂n)。
  • 既然不同底数都可以转化，那就直接使用 O(logn) 来标记对数阶。

而对于 O(nlogn) 就是一段时间复杂度为 O(logn) 的代码段被执行了 n 次。

多参数阶 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;
}

• 其时间复杂度为：O(m+n)
• 对于加法规则（变了）：T1(m) + T2(n) = O(f(m) + g(n))。
• 对于乘法规则（不变）：T1(m)*T2(n) = O(f(m) * f(n))。

空间复杂度分析

空间复杂度。关联到资源消耗。

• 空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。

使用大 O 表示法，和时间复杂度一样，只是分析的数据规模 n 由时间度量改为空间度量。

小结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系。

通常越高阶复杂度的算法，执行效率越低。

常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n² )。