跳到主要内容

1.3-复杂度分析

Create by fall on 30 Jan 2022
Recently revised in 17 Apr 2025

算法复杂度分析​

迭代​

在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。

循环是最常见的迭代形式之一，适合在预先知道迭代次数时使用。

/* for 循环 typescript */
function forLoop(n: number): number {
    let res = 0;
    // 循环求和 1, 2, ..., n-1, n
    for (let i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
/* for 循环 */
fn for_loop(n: i32) -> i32 {
    let mut res = 0;
    // 循环求和 1, 2, ..., n-1, n
    for i in 1..=n {
        res += i;
    }
    res
}
fn for_loop(n:i32)-> i32{
  let mut res = 0;
  for i in 1..=n{
    res +=i;
  }
  res
}

此求和函数的操作数量与输入数据大小 n 成正比，成“线性关系”，即输入越大，时间复杂度相应成比例增大。

while 循环更加灵活，可以多次修改条件 i

/* while 循环 Rust */
fn while_loop_two (n:i32)->i32{
  let mut res:i32 = 0;
  let mut i = 1;
  while i<=n{
    res+=i;
    i+=1;
    i*=2;
  }
  res
}

循环的嵌套

fn nested_loop_for(n:i32)->String{
  let mut res = vec![];
  for i in 1..n{
    for j in 1..j{
      res.push(format!("({},{}), " ,i,j))
    }
  }
  res.join("")
}

对比没有嵌套时，有一层嵌套，操作数量从 n 变为 n*n，

递归​

递归，通过调用函数本身来解决问题，

  • 递：不断调用自身，传入更小或更简化的参数，知道达成“终止条件”
  • 归：触发终止条件后，程序从最深层函数开始逐渐返回，汇聚每层的结果

实现时主要包含三个要素

  • 终止条件：用于决定什么时候由“递”转“归”。
  • 递归调用：对应“递”，函数调用自身，通常输入更小或更简化的参数。
  • 返回结果：对应“归”，将当前递归层级的结果返回至上一层。
fn recur(n:i32)->i32{
  
  if n ==1 {
    return 1
  }
  let res = n + recur(n-1);
  res
}

该函数的递归深度为 n 。

  • 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。
  • 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到基本情况时停止（基本情况的解是已知的）。

它们代表了两种完全不同的思考和解决问题的范式。

以上述求和函数为例，设问题 f(n)=1+2+⋯+n 。

  • 迭代：在循环中模拟求和过程，从 1 遍历到 n ，每轮执行求和操作，即可求得 f(n) 。
  • 递归：将问题分解为子问题 f(n)=n+f(n−1) ，不断（递归地）分解下去，直至基本情况 f(1)=1 时终止。

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。这将导致两方面的结果。

  • 函数的上下文数据都存储在称为“栈帧空间”的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加耗费内存空间。
  • 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。
  • 在实际中，编程语言允许的递归深度通常是有限的，过深的递归可能导致栈溢出错误。

尾递归​

如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。

fn tail_recur(n:i32,res:i32)->i32{
  if n==0 {
    return res
  }
  tail_recur(n-1,n+res)
}
  • 普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。
  • 尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

请注意，许多编译器或解释器并不支持尾递归优化。例如，Python 默认不支持尾递归优化，因此即使函数是尾递归形式，仍然可能会遇到栈溢出问题。

递归树​

处理拆分任务时，递归往往比迭代的思路更加直观、代码更加易读。

例如斐波那契数列

fn fib(n:i32)->i32{
  // 斐波那契数列前两位为 1 时
  if n==1||n==2{
    return 1;
  }
  let res = fib(n-1) + fib(n-2);
  res
}

fn fib2(n:i32,a:i32 = 1,b:i32 = 1)->{
  if(n<0){
    return 0; 
  }
  if n ==1||n==2{
    return 1;
  }
  // 把 a 当作 n-1，b 为 n-2
  let a = b + fib2(n-3);
  let b = fib2(n-3) + fib2(n-4);
  n = a+b
}
  • 从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或间接地应用了这种思维方式。
  • 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

时间复杂度​

常见的时间复杂度类型

  • 常数阶：O(1)
  • 线性阶：O(n) 。
  • 平方阶：O(n2)
  • 指数阶：O(2n)
  • 对数阶：O(log⁡n)
  • 线性对数阶：O(nlog⁡n)
  • 阶乘阶：O(n!)

最差、最佳、平均时间复杂度：

  • 最差时间复杂度 O(n)
  • 最佳时间复杂度 Ω(1)

实际中很少使用最佳时间复杂度，而最差时间复杂度更为实用，因为它给出了一个效率安全值

对于较为复杂的算法，计算平均时间复杂度往往比较困难，因为很难分析出在数据分布下的整体数学期望。在这种情况下，通常使用最差时间复杂度作为算法效率的评判标准。

空间复杂度​

这个概念与时间复杂度非常类似，只需将“运行时间”替换为“占用内存空间”。

内存空间主要包括以下几种

  • 输入空间：存储算法的输入数据
  • 暂存空间：存储算法运行过程中的变量，对象，函数上下文
    • 暂存数据：运算过程中的各种常量，变量，对象
    • 栈帧空间：保存调用函数的上下文数据，每次调用都会在栈顶部创建一个栈帧
    • 指令空间：保存编译后的程序指令，通常忽略不计
  • 输出空间：存储算法的输出数据
// rust
use std::rc::RC
use std::cell::RefCell

struct Node{
  val: i32
  next:Option<Rc<RefCell<Node>>>
}
impl Node{
  fn new(val:i32)->Self{
    Self {val:val,next:None}
  }
}

fn function()-> i32{
  // 执行操作
  return 0;
}
fn algorithm(n:i32)->i32{   // 输入数据
  const a:i32 = 0;          // 暂存数据（常量
  let mut b = 0;            // 暂存数据（变量
  let node = Node::new(0);  // 暂存数据（对象）
  let c = function()        // 栈帧空间（调用函数
  return a + b +c;          // 输出数据
}

推算

我们通常只关注最差空间复杂度。这是因为内存空间是一项硬性要求，我们必须确保在所有输入数据下都有足够的内存空间预留。

  • 以最差输入数据为准：当 n < 10，空间复杂度为 O(1) 当 n > 10 时，初始化数组占用 O(n) 空间，因此空间复杂度为 O(n)
  • 以运行中的峰值内存为准：例如，程序在执行最后一行之前，占用 O(1) 空间；当初始化数组 nums 时，程序占用 O(n) 空间，因此最差空间复杂度为 O(n)。

常见空间复杂度​

  • 常数阶：O(1)，在循环中初始化变量或调用函数而占用的内存，下一循环会释放，因此为 O(1)
  • 线性阶：O(n)，元素数量与 n 成正比的数组，链表，栈，队列等。
  • 平方阶：O(n2)，常见于矩阵和图
  • 指数阶：O(2n)，常见于二叉树
  • 对数阶：O(logn)，用于常见分支算法，例如归并排序

权衡时间与空间​

理想情况下，我们希望算法的时间复杂度和空间复杂度都能达到最优。然而在实际情况中，同时优化时间复杂度和空间复杂度通常非常困难。

降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。我们将牺牲内存空间来提升算法运行速度的思路称为“以空间换时间”；反之，则称为“以时间换空间”。

选择哪种思路取决于我们更看重哪个方面。在大多数情况下，时间比空间更宝贵，因此“以空间换时间”通常是更常用的策略。当然，在数据量很大的情况下，控制空间复杂度也非常重要。