递归式T(n)=7T(n/2)+n²时间复杂度求解正确性验证求助

先直接给结论：你的推导过程完全正确，出现负项是积分计算的正常中间结果，不影响最终时间复杂度的结论。

一步步拆解验证 #

• 求特征指数$p$
  对应递归式参数：$a=7$，$b=2$，解方程$7*(2^{{-p})=1$，即$2}p=7$，得到$p=\log_2 7\approx2.807$，这一步逻辑没问题。

• 积分项计算
  Akra-Bazzi核心公式为$T(n)=\Theta\left(n^{p\left(1+\int_1}n \frac{f(x)}{x^{{p+1}}dx\right)\right)$，代入$f(x)=x²$后，积分转化为$\int_1}n x^{1-p}dx$。
  因为$1-p=1-\log_27$是负数，积分结果为$\frac{n^{{2-p}-1}{2-p}$。这里$2-p$同样为负（因$p>2$），所以积分项看起来会带负号，但当$n\to\infty$时，$n}{2-p}=n^{-(p-2)}$会趋近于0，此时积分项的极限是$\frac{-1}{2-p}=\frac{1}{p-2}$，是一个正的常数。

• 最终复杂度结论
  把积分结果代回公式后，会得到包含$n^2$和$np$的表达式，但由于$p=\log_27>2$，$n^{p$的增长速度远快于$n²$，低阶的$n²$项可以直接忽略，最终时间复杂度为$\Theta(n}{\log_27})$，和WolframAlpha的结果一致。

关于负项的疑惑解答 #

你看到的负项只是积分计算过程中的中间产物，并非推导错误。当$n$趋向无穷大时，带负号的小项会趋近于0，不会动摇$n^p$作为主导项的地位，所以你的推导逻辑完全成立。

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