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
}

从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略直接或间接地应用了这种思维方式。
从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分析。

算法复杂度分析​

迭代​

递归​

尾递归​

递归树​

算法复杂度分析

迭代

递归

尾递归

递归树