我被困在这个问题上，我不知道如何解决它，不管我尝试什么，我就是找不到一种方法来处理这个函数，所以我可以用一种方法来表示它，让我找到一个g（n），所以g（n）是t（n）∈Θ（g（n））
我遇到的问题是：
$T(n)=4n^4T(\sqrt n) +(n^6lgn+3lg^7n)(2n^2lgn+lg^3n)。$
另外，如果你能-你能检查一下我是否在正确的道路上：
$T(n)=T(n-1)+\frac{1}{n}+\frac{1}{n^2}。$
为了解决这个问题，我尝试使用：$T(n)-T(n-1)=\frac{1}{n}+\frac{1}{n^2}$iff$(T(n)-T(n-1))+(T(n-1)-T(n-2))+\ldots+(T(2)-T(1))=\frac{1}{n}+\frac{1}{n-1}+...+\frac{1}{n^2}+\frac{1}{\left(n-1\right)^2}+....$iff$(T(n)-T(n-1))+(T(n-1)-T(n-2))+\ldots+(T(2)-T(1))=T(n)=T(1)+\sum_{k=2}^n\frac{1}{n}+\sum_{k=2}^n\frac{1}{n^2}$，然后使用谐波级数公式。但是我不知道如何继续并完成它，并找到解决它的渐近边界
我希望在第二天我走上了正确的道路。但是我根本不知道如何解决第一个问题。如果我犯了什么错误，请告诉我正确的方法，这样我就能改进我的错误。
非常感谢你的帮助
抱歉，由于某种原因，这里的数学不正确
最佳答案
评论如下：
先解决（2），因为它更简单。
您的扩展尝试是正确的。写得稍微有点不同：
A，调和级数-渐近等于自然对数：γ = 0.57721...是指Euler-Mascheroni constant。
逆平方和-无穷和是著名的Basel problem：
即1.6449...。因此，由于b是单调增加的，它总是O(1)。
（2）的复杂度仅为Θ(log n)。
（1）有点乏味。
严格的低复杂性类，即：
假设一组N函数{F_i}按复杂度递减顺序排序，即F2 = o(F1)等。
因此，不同函数之和渐近等于具有最高增长率的函数之和。
要对两个括号的展开式中的术语进行排序，请注意
可通过应用L'Hopital's rule证明所以唯一渐近有效项是n^6 log n * 2n^2 log n = 2n^8 log^2 n。
如前所述展开求和，注意i）因子4n^4累加，ii）第m次展开的参数为n^(1/(2^m))（重复平方根）。
因此，由第m-扩展添加的新术语是（假设您知道如何这样做，因为您可以对（2）执行相同的操作）：
令人惊讶的是，每增加一个术语都与第一个完全相等。
假设递归展开的停止条件是n < 2（当然，这会舍入到T(1)）：
由于每个附加项t_m总是相同的，只需乘以最大扩展数：
功能（1）是
关于algorithm - 渐近(递归)函数困难(算法分析)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49990600/