使用迭代法求解递推式T(n)的算法复杂度分析

咱们一步步拆解这个递推式的求解过程，先明确已知条件：递推式为
$$T(n) = T\left(\frac{n}{2}\right) + n \left(\sin\left(n-\frac{π}{2}\right) +2\right)$$
初始条件 $T(1) = 1$。

迭代展开过程 #

首先对递推式进行迭代展开，每次把$T\left(\frac{n}{2^k}\right)$替换成下一层的表达式：
\begin{align*}
T(n) &= T\left(\frac{n}{2}\right) + n \left(\sin\left(n-\frac{π}{2}\right) +2\right) \\
&= T\left(\frac{n}{2^2}\right) + \frac{n}{2} \left(\sin\left(\frac{n}{2}-\frac{π}{2}\right) +2\right) + n \left(\sin\left(n-\frac{π}{2}\right) +2\right) \\
&= T\left(\frac{n}{2^3}\right) + \frac{n}{2^2} \left(\sin\left(\frac{n}{2^2}-\frac{π}{2}\right) +2\right) + \frac{n}{2} \left(\sin\left(\frac{n}{2}-\frac{π}{2}\right) +2\right) + n \left(\sin\left(n-\frac{π}{2}\right) +2\right) \\
&\vdots \\
&= T\left(\frac{n}{2^k}\right) + \sum_{i=0}^{k-1} \frac{n}{2^i} \left( \sin\left(\frac{n}{2^i} - \frac{π}{2}\right) + 2 \right)
\end{align*}

当迭代到$2^k = n$时（也就是$k = \log_2 n$），此时$\frac{n}{2^k} = 1$，代入初始条件$T(1)=1$，递推式就变成：
$$T(n) = 1 + \sum_{i=0}^{\log_2 n -1} \frac{n}{2^i} \left( \sin\left(\frac{n}{2^i} - \frac{π}{2}\right) + 2 \right)$$

拆分求和项分析复杂度 #

我们把求和项拆成两部分分别计算：
$$\sum_{i=0}^{\log_2 n -1} \frac{n}{2^i} \left( \sin\left(\frac{n}{2^i} - \frac{π}{2}\right) + 2 \right) = n\sum_{i=0}^{\log_2 n -1} \frac{1}{2^{i}\sin\left(\frac{n}{2}i} - \frac{π}{2}\right) + 2n\sum_{i=0}^{\log_2 n -1} \frac{1}{2^i}$$

1. 计算第二部分的等比数列和

第二部分是标准的等比数列求和：
$$\sum_{i=0}^{\log_2 n -1} \frac{1}{2^i} = 2 - \frac{1}{2^{\log_2 n -1}} = 2 - \frac{2}{n}$$
代入后得到：
$$2n \times \left(2 - \frac{2}{n}\right) = 4n - 4$$

2. 分析第一部分的有界性

对于正弦函数，我们知道$\sin(x)$的取值范围始终是$[-1, 1]$，因此：
$$\left| \frac{1}{2^{i}\sin\left(\frac{n}{2}i} - \frac{π}{2}\right) \right| ≤ \frac{1}{2^i}$$
那么第一部分的求和绝对值满足：
$$\left| \sum_{i=0}^{\log_2 n -1} \frac{1}{2^{i}\sin\left(\frac{n}{2}i} - \frac{π}{2}\right) \right| ≤ \sum_{i=0}^{\log_2 n -1} \frac{1}{2^i} < \sum_{i=0}^{\infty} \frac{1}{2^i} = 2$$
这说明第一部分的求和是一个有界常数，因此$n$乘以这个有界值的结果是$O(n)$量级。

最终复杂度结论 #

把两部分结果和初始的1合并：
$$T(n) = 1 + (O(n)) + (4n - 4) = O(n)$$
也就是说，这个递推式对应的算法复杂度是线性时间复杂度$O(n)$。

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