求解含平方项的递推关系式及算法时间复杂度分析求助

换元法的正确姿势 #

你之前用$m=2^k$的换元失效，大概率是因为递推式里的平方项和根号项组合，需要用嵌套指数换元而非简单的线性指数换元。下面以最常见的两类含平方项递推式为例讲解：

场景1：递推式含$T(\sqrt{n})$的平方

比如典型形式：$T(n) = (T(\sqrt{n}))^2 + C$（$C$为常数，边界条件如$T(2)=1$）

• 令 $n = 2^{2k}$，则$\sqrt{n} = 2^{2{k-1}}$，记$S(k) = T(2^{2k})$，代入后递推式变为：

  S(k) = (S(k-1))^2 + C
  

• 分情况求解：
  • 若$C=0$：$S(k) = (S(k-1))^2$，结合$S(0)=1$，得$S(k)=1$，回代后$T(n)=1$，复杂度$O(1)$。
  • 若$C=1$：代入边界条件$S(0)=1$，可递推得$S(1)=2$，$S(2)=5$，$S(3)=26$，归纳可得$S(k)=2^{2k}-1$，回代$k=\log_2(\log_2 n)$，得$T(n)=n-1$，复杂度$O(n)$。

场景2：递推式含$T(n/b)$的平方

比如形式：$T(n) = (T(n/2))^2 + n$（边界条件如$T(1)=1$）

• 令$n=2^{k$，记$S(k)=T(2}k)$，代入得：

  S(k) = (S(k-1))^2 + 2^k
  

• 这类递推的增长速度是双指数级：比如$S(0)=1$，$S(1)=3$，$S(2)=13$，$S(3)=177$，$S(4)=31345$，复杂度为$O(2^{2n})$，属于极端低效的算法类型。

关键提示 #

如果你的递推式是其他形式（比如平方项在自变量上，或者和其他项组合），把具体表达式贴出来，能给出更精准的解法。

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