求解Big-Theta表示的递推式，求助(b)(c)小题解题方法

首先先明确图中(b)(c)对应的递推式及边界条件：

• (b)：T(n) = 2T(n/2) + n / log n，边界T(1) = 1
• (c)：T(n) = T(n-1) + 1/n，边界T(1) = 1

这个递推确实不符合主定理适用条件，因为$f(n) = n/log n$和$n^{log_b a}=n^1$的差异不是多项式级别的，我们用递归树法求解：

• 递归树第0层（根节点）总代价：$n / log_2 n$
• 第1层共2个节点，每个节点规模为$n/2$，总代价：$2 \times \frac{n/2}{log_2(n/2)} = \frac{n}{log_2 n - 1}$
• 第i层共$2^{i$个节点，每个节点规模为$n/2}i$，总代价：$2^i \times \frac{n/2^i}{log_2(n/2i)} = \frac{n}{log_2 n - i}$
• 递归到$n/2^k = 1$时终止，总层数$k = log_2 n$

总时间复杂度为各层代价求和：
$$T(n) = \sum_{i=0}^{log_2 n -1} \frac{n}{log_2 n -i} = n \times \sum_{m=1}^{log_2 n} \frac{1}{m}$$
其中$m = log_2 n -i$，求和项是调和级数，$H_{log_2 n} = O(log log n)$，因此最终$T(n) = O(n log log n)$。

代入法验证：假设存在常数$c>0$使得$T(n) \leq c n log log n$，代入递推式：
$$T(n) \leq 2c \times \frac{n}{2} log log(\frac{n}{2}) + \frac{n}{log n} = c n log(log n - 1) + \frac{n}{log n}$$
利用近似$log(log n -1) = log(log n (1 - \frac{1}{log n})) = log log n + log(1-\frac{1}{log n}) \leq log log n - \frac{1}{log n}$，代入后：
$$T(n) \leq c n log log n - \frac{c n}{log n} + \frac{n}{log n}$$
取$c \geq 1$即可满足不等式，假设成立。

这个递推是典型的累加型递推，直接展开即可：
$$T(n) = T(n-1) + \frac{1}{n} = T(n-2) + \frac{1}{n-1} + \frac{1}{n} = ... = T(1) + \sum_{k=2}^n \frac{1}{k}$$
求和项依然是调和级数，$H_n = 1 + \sum_{k=2}^n \frac{1}{k} = O(log n)$，因此最终$T(n) = O(log n)$。

代入法验证：假设存在常数$c>0$使得$T(n) \leq c log n$，代入递推式：
$$T(n) \leq c log(n-1) + \frac{1}{n} = c log(n(1-\frac{1}{n})) + \frac{1}{n} = c log n + c log(1-\frac{1}{n}) + \frac{1}{n}$$
利用近似$log(1-\frac{1}{n}) \leq -\frac{1}{n}$，代入后：
$$T(n) \leq c log n - \frac{c}{n} + \frac{1}{n}$$
取$c \geq 1$即可满足不等式，假设成立。

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