如何计算含嵌套循环与递归函数的代码时间复杂度？

1. 递归函数compute(a, b)的复杂度 #

compute是线性递归逻辑：每次调用compute(a,b)都会递归调用compute(a,b-1)，直到b=0触发基准条件。对于给定的b，递归总调用次数为b+1次（从b逐层降到0），每次递归仅包含简单加法和返回操作，因此时间复杂度为O(b)。

2. 嵌套循环的总复杂度 #

• 外层循环：i从1开始，每次乘2直到i <=n，循环次数为log₂n + 1次（比如n=8时，i取1、2、4、8，共4次），量级为O(logn)。
• 内层循环：对于每个i，j从0到i-1，共执行i次。每次调用compute(i,j)的复杂度是O(j)，因此单个i对应的内层循环总操作量是0+1+2+...+(i-1)，求和结果为i*(i-1)/2，量级为O(i²)。

将外层循环所有i的操作量累加，i的取值为1、2、4、8、...、2^k（其中2k ≤n），对应的平方和为：
1² + 2² + 4² + 8² + ... + (2^k)²

这是首项为1、公比为4的等比数列，求和结果为(4^(k+1)-1)/3。由于2^k ≤n，可得4^(k+1)=4*(2^k)² ≤4n²，因此整个和的量级为O(n²)。

结论 #

整体代码的时间复杂度为O(n²)，递归函数的线性复杂度已被嵌套循环的平方级累加主导，最终复杂度由n的平方项决定。

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