algorithm - 困难的渐近(递归)函数(算法分析)

Question

我被困在这个问题上，我不知道如何解决它，无论我尝试什么，我都找不到一种方法来使用这个函数，所以我可以用一种允许我的方式来表示它找到一个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}$ 然后使用调和级数公式。但是我不知道如何继续并完成它并找到渐近边界来解决它

我希望第二次我走在正确的道路上。但是我根本不知道如何解决第一个问题。如果我犯了任何错误，请告诉我正确的方法，以便我改进我的错误。

非常感谢你的帮助

抱歉，由于某些原因，这里的数学显示不正确

Answer 1

根据评论:

---

首先解决(2)，因为它更直接。

您的扩展尝试是正确的。写法略有不同:

• A，调和级数-渐近等于自然对数:

  

  γ = 0.57721...是Euler-Mascheroni constant .

• B，平方反比和——无穷和就是著名的Basel problem :

  

  这是1.6449... .因此，由于 B 是单调递增的，它总是 O(1) .

The total complexity of (2) is simply Θ(log n).

---

(1) 有点乏味。

• Little-o 表示法:严格 较低复杂度类，即:

  

• 假设一组 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 的参数-th 扩展是 n^(1/(2^m)) (重复平方根)。

  由 m 添加的新术语-因此扩展是(假设您知道如何执行此操作，因为您能够为 (2) 执行相同的操作):

  

  令人惊讶的是，每个添加的项都与第一个项完全相等。

• 假设递归展开的停止条件是n < 2 (当然四舍五入为 T(1) ):

  

  由于每个添加的术语 t_m始终相同，只需乘以最大扩展数:

Function (1) is