如何确定含分支路径的随机算法的递推方程与时间复杂度？

算力阿峰

2026-7-25

随机算法递推方程与时间复杂度分析疑问

在算法分析课程中，我们需要确定随机算法的递推方程，但我不清楚如何处理存在两条不同执行路径的算法。例如考虑以下算法：

Algorithm foo (A[1...n])
if n=1 return 0;
else if(n%2=0) return 2*foo(A[1....n/3])
else return foo(A[1....n/3])

我给出的解法为：

随后我用主定理计算时间复杂度：

我知道这两种结果都不正确，恳请指导如何确定随机算法的递推方程与时间复杂度？

问题分析与解答

首先要明确：你给出的算法不是随机算法，它的分支由输入规模n的奇偶性决定，属于确定性算法的多分支递推问题。你之前的错误在于把单次分支的n奇偶性单独计算复杂度，忽略了递归过程中n的演化规律，以及奇偶分支的递归链不会直接终止。

针对这个确定性算法，需要从最坏、最好、平均情况分别分析：

最坏情况：假设每次递归时n都是偶数，递推式为：
T(n) = 2T(n/3) + 1（n>1），T(1)=1
用主定理：a=2，b=3，f(n)=1。由于n^log₃2 ≈ n^0.630 > f(n)，因此最坏情况复杂度为Θ(n^log₃2)。
最好情况：假设每次递归时n都是奇数，递推式为：
T(n) = T(n/3) + 1（n>1），T(1)=1
展开递推可得：T(n) = T(n/3^k) + k，当n/3^k=1时，k=log₃n，因此T(n)=log₃n +1，即复杂度为Θ(log n)——你之前误以为是Θ(1)，是错误地认为奇数n会直接终止递归，但实际上仍会递归到n/3，直到n=1。
平均情况：如果假设递归过程中n为奇偶的概率各为50%（近似输入分布随机），则需要用期望递推：设E[T(n)]为期望时间复杂度，递推式为：
```
E[T(n)] = 1 + 0.5*2*E[T(n/3)] + 0.5*1*E[T(n/3)] = 1 + 1.5*E[T(n/3)]
E[T(1)] = 1
```
用主定理：a=1.5，b=3，f(n)=1。由于n^log₃1.5 ≈ n^0.369 > f(n)，因此期望复杂度为**Θ(n^{log₃1.5)**，约等于Θ(n}0.37)。

如果算法是真正的随机算法（比如通过随机函数选择分支，而非依赖n的奇偶性），则直接使用上述期望递推方程即可：将每个分支的执行概率作为权重，合并成单一的期望递推式，再用主定理或递推展开法求解。

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