如何计算递推关系T(n)=0.5T(n/2)+1/n的复杂度（主定理a<1失效场景）

该递推关系的复杂度 #

我们可以直接通过迭代展开计算：
逐层展开递推式可得：

T(n) = 1/n + 0.5 * T(n/2)
= 1/n + 0.5 * (2/n + 0.5 * T(n/4)) = 1/n + 1/n + 0.25 * T(n/4)
= 1/n + 1/n + 1/n + 0.125 * T(n/8)
...

展开k次后，递推式变为：
T(n) = k*(1/n) + (0.5)^k * T(n/(2^k))
当递归到边界条件 n/(2^k) = 1 时停止迭代，此时 k = log2(n)，代入可得：
T(n) = log2(n)/n + (1/n) * T(1)
其中T(1)是常数边界值。
从结果可以得出：

• 紧确渐近界为 Θ(log n / n)
• 由于log n / n是随n增大单调递减的函数，所有取值都小于固定常数，因此也可以认为存在O(1)的上界。

a<1时主定理失效的替代解法 #

主定理的适用前提是分治递推式中a≥1（a对应分治算法的子问题个数，实际场景下子问题个数不可能小于1），因此a<1的场景不在主定理的覆盖范围内，这类场景常用两种方法计算复杂度：

• 迭代展开法：就是上述计算用到的方法，将递推式逐层展开为非递归项的求和式，化简求和结果的量级后叠加边界项的量级，就能得到最终复杂度。
• 替换归纳法：先预判复杂度的大致上界/下界，再通过数学归纳法验证预判的正确性，适合对递推量级有初步判断的场景。

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