本文通过逐层拆解一个三路递归 java 函数，系统讲解如何准确分析其时间复杂度；重点揭示无剪枝、无记忆化的朴素递归如何导致指数级增长，并给出递推关系建模与渐近阶判定的完整方法。
本文通过逐层拆解一个三路递归 java 函数，系统讲解如何准确分析其时间复杂度；重点揭示无剪枝、无记忆化的朴素递归如何导致指数级增长，并给出递推关系建模与渐近阶判定的完整方法。
该函数 fun1 是典型的无优化递归实现，其结构看似简洁，但隐藏着极高的时间开销。我们先明确核心观察点：函数体内不含任何循环，所有操作（比较、赋值、返回）均为常数时间 —— 即非递归部分的时间复杂度为 O(1)。真正决定整体性能的是递归调用本身：
int m1 = fun1(arr, index - 1); // 分支1 int m2 = fun1(arr, index - 2); // 分支2 int m3 = fun1(arr, index - 4); // 分支3
每次调用都会触发最多 3 次递归调用，且各分支的输入规模分别减小为 index−1、index−2 和 index−4。虽然减量不同，但在大 O 分析中，常数偏移与系数均被忽略，因此三者均可视为对规模 n 的线性缩减（即子问题规模仍为 Θ(n) 级别）。关键在于：每层递归产生 3 个子问题，而递归深度由 index 决定 —— 最坏情况下（如 index = n），递归树高度为 n（因每次至少减 1）。
由此可建立递推式（设 T(n) 表示输入为 n 时的最坏时间复杂度）：
T(n) = T(n−1) + T(n−2) + T(n−4) + O(1)
为估算渐近上界，我们放宽约束：因 T(n−2) ≤ T(n−1) 且 T(n−4) ≤ T(n−1)，故有：
T(n) ≤ 3·T(n−1) + c （c 为常数）
反复展开该不等式：
T(n) ≤ 3·T(n−1) + c
≤ 3·[3·T(n−2) + c] + c = 3²·T(n−2) + 3c + c
≤ 3³·T(n−3) + 3²c + 3c + c
…
≤ 3ⁿ·T(0) + c·(3ⁿ⁻¹ + 3ⁿ⁻² + … + 1)
= O(3ⁿ)
几何级数求和项 Σₖ₌₀ⁿ⁻¹ 3ᵏ = (3ⁿ − 1)/2 = O(3ⁿ)，主导项仍是 3ⁿ。因此，该算法的时间复杂度为 O(3ⁿ) —— 典型的指数级复杂度。
⚠️ 重要提醒：
- 此复杂度源于重复计算：fun1(arr, k) 被多次以相同 k 值调用（如 fun1(n−3) 可能同时出现在 n−1 和 n−2 的子调用链中），未做缓存；
- 实际运行时，n = 40 已导致数万亿次调用，程序几乎不可用；
- 优化方向明确：引入记忆化（Memoization）可将时间复杂度降至 O(n)，空间复杂度 O(n)；若改用自底向上动态规划，还可优化空间至 O(1)（需注意状态依赖跨度为 4，需保留最近 4 个值）。
总结：分析递归复杂度，核心是识别分支因子与递归深度。当分支因子恒定（如本例为 3）且无剪枝/重用时，复杂度通常为 O(分支因子^深度)。切勿被减法常数（如 −2、−4）干扰判断——它们只影响常数因子，不改变指数级本质。
