困难的渐近（递归）函数（算法分析）
difficult asymptotic(recurrence) function (algorithm analysis)
我被困在这个问题上，我不知道如何解决它，无论我尝试什么，我都找不到一种方法来使用这个函数，所以我可以用一种方式来表示它请允许我找到一个 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.
B,平方反比和——无穷和就是著名的Basel problem:
即1.6449...。因此，由于 B 是单调递增的，它总是 O(1).
The total complexity of (2) is simply Θ(log n).
(1)有点乏味。
Little-o 表示法：strictly 降低复杂度class，即：
假设一组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 总是相同的，只需乘以最大扩展数即可：
Function (1) is
我被困在这个问题上，我不知道如何解决它，无论我尝试什么，我都找不到一种方法来使用这个函数，所以我可以用一种方式来表示它请允许我找到一个 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.B,平方反比和——无穷和就是著名的Basel problem:
即
1.6449...。因此，由于 B 是单调递增的，它总是O(1).
The total complexity of (2) is simply
Θ(log n).
(1)有点乏味。
Little-o 表示法：strictly 降低复杂度class，即：
假设一组
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总是相同的，只需乘以最大扩展数即可：
Function (1) is