如何求解嵌套循环与递归函数的Big O复杂度？附学习及面试指南

不用死记复杂数学，按这几步来就行：

• 拆分代码块：把代码拆成顺序执行、循环、条件分支、递归这些独立部分，逐个算复杂度再合并。
• 顺序执行的块：直接取复杂度最高的那个，因为Big O只看主导项。比如先执行O(n)的循环再执行O(1)的赋值，整体还是O(n)。
• 循环处理：
  • 单层循环：看循环次数和输入n的关系。比如for(i=0;i<n;i++)是O(n)；如果是每次除以2/乘以2，就是O(log n)。
  • 嵌套循环：如果内层循环次数和外层变量有关，就把每次内层的次数加起来；如果无关，就把内外层的复杂度相乘。比如外层O(n)、内层固定O(n)就是O(n²)，但像示例这种内层次数随外层变的，就得求和。
• 条件分支：取分支里复杂度最高的那个，因为Big O考虑最坏情况。比如if分支是O(n)，else分支是O(1)，整体按O(n)算。
• 递归处理：入门级的话，要么数递归调用次数，要么用递归树看总操作数；熟一点可以用主定理，但不用抠太细的数学证明，记住常见场景就行（比如每次拆成2个子问题、每个子问题规模是n/2，就是O(n log n)）。
• 最后合并：去掉常数、系数和低阶项，只留主导项。比如2n+5logn+3，直接写成O(n)。

其实不用高深数学，入门门槛很低：

• 前置知识：初中数学的四则运算、指数、对数基本概念就行，知道log₂n是“把n拆成多少次2相乘”就行。
• 核心技能：
  • 等比/等差数列求和：比如算嵌套循环的总操作数时，经常用到n + n/2 + n/4 + ...这种等比数列，记住求和结果趋近于2n就行，不用推导公式。
  • 对数的基本理解：能判断“每次除以k的循环次数是O(log_k n)”，而且知道log的底数不影响Big O（因为log_k n = log₂n / log₂k，系数可以去掉）。
  • 渐近增长的直观判断：能分清O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)的增长速度，知道谁是主导项。
  • 简单递推思维：能把递归函数转化成“每次调用做了多少操作，子问题规模是多少”的递推式，比如斐波那契递归是T(n)=T(n-1)+T(n-2)+O(1)。

面试不会考太偏的，重点抓这些：

• 必掌握：能快速分析常见结构的复杂度，比如：
  • 常数操作（赋值、简单计算）：O(1)
  • 单层线性循环：O(n)
  • 二分/减半类循环：O(log n)
  • 普通嵌套循环（内外层都是n）：O(n²)
  • 归并排序/快速排序平均：O(n log n)
  • 递归斐波那契：O(2ⁿ)
• 进阶要求：能处理像示例这种内层循环次数随外层变化的情况，能区分最好、最坏、平均复杂度（比如快速排序最坏是O(n²)，平均是O(n log n)），能用主定理分析简单递归（比如二叉树遍历是O(n)，因为每个节点访问一次）。
• 避坑：别一看到嵌套循环就说O(n²)，得看内层循环的次数和外层的关系；递归别漏算调用次数，比如递归遍历链表是O(n)不是O(log n)。

先看代码：

int fun(int n) {
  int count = 0;
  for (i = n; i > 0; i /= 2) {
    for (j = 0; j < i; j++) {
      count += 1;
    }
  }
  return count;
}

分析步骤：

1. 外层循环：i从n开始，每次除以2，直到i>0，循环次数是log₂n次左右（比如n=8时，i=8→4→2→1，共4次，log₂8=3，加1是4，忽略常数就是O(log n)）。
2. 内层循环：每次外层循环时，内层循环i次，也就是第一次n次，第二次n/2次，第三次n/4次，直到最后1次。
3. 总操作次数：n + n/2 + n/4 + ... + 1，这是等比数列求和，结果是2n - 1（当n很大时，1可以忽略，就是2n）。
4. 最后取主导项，去掉系数2，所以时间复杂度是O(n)。

内容的提问来源于stack exchange，提问作者Abraam