含循环内递归调用的递归函数时间复杂度求解

首先明确递推关系：
函数fun(n)的执行逻辑是打印n（O(1)开销），然后循环i从n到2，每次调用fun(i/2)。因此时间复杂度的递推式为：

T(n) = 1 + sum_{i=2}^n T(floor(i/2))  ，其中T(1)=1（仅打印1）

简化递推式 #

通过计算T(n)与T(n-1)的差值，可以大幅简化递推关系：

• T(n-1) = 1 + sum_{i=2}^{n-1} T(floor(i/2))
• 两式相减得：T(n) - T(n-1) = T(floor(n/2))

最终递推式简化为：

T(n) = T(n-1) + T(floor(n/2))  ，T(1)=1

分析渐近行为 #

这个递推式的增长速度介于多项式和指数函数之间，属于亚指数级增长，具体分析如下：

1. 上界分析：
   由于T(n)是严格递增函数，T(floor(n/2)) ≤ T(n-1)，因此T(n) ≤ 2T(n-1)，解得T(n) = O(2^n)，但这是非常宽松的上界。更紧的上界可证明为T(n) = exp(O(√(log n log log n)))。

2. 下界分析：
   利用函数递增性可推导出，T(n)的增长速度比任何多项式n^k都快，精确下界为T(n) = exp(Ω(√(log n log log n)))。

递归树直观理解 #

递归树的最大高度确实是log n，但每层节点数的增长并非线性：

• 第0层（根节点）：1个节点，对应fun(n)
• 第1层：n-1个节点，对应fun(n/2), fun((n-1)/2), ..., fun(1)
• 第2层：每个第1层的节点fun(k)会生成k-1个子节点，总节点数为sum_{i=2}^n (floor(i/2)-1)，这个和的增长速度远快于线性，最终导致整体时间复杂度呈现亚指数增长。

结论 #

该函数的时间复杂度为亚指数级，精确表达式为T(n) = Θ(exp(√(log n log log n)))——简单来说就是增长速度比任何多项式都快，但比指数函数2^n慢。

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