解决复发方程由substituion [英] Solving recurrence equation by substituion

问题描述

我试图解决 T（N）=开方（N）* T（开方（N））+ SQRT（N）通过绘制reccurence树和解决它是替代方法。但我有一个很难包装我的头周围的sqrt方法将如何影响这一进程，我要寻找一些指针如果可能的话

I am trying to solve T(n) = sqrt(n)*T(sqrt(n))+sqrt(n) by drawing a reccurence tree and solving it be the substitution method. But I am having a hard time wrapping my head around how the sqrt method will affect this process and I am looking for some pointers if possible

许多AP preciated！

Much appreciated!

推荐答案

您可以写 T（N）=开方（N）⋅T（开方（N））+ SQRT（N）为

T(n) = n1/2 + n3/4 + n7/8 + ...

我们知道Σ<子> I = 1，...，∞ 2 -i = 1 ，所以你可以说

We know Σi=1,...,∞ 2-i = 1, so you can say

T(n) = n1/2 + n3/4 + n7/8 + ... < n + n + n + ...

现在你只需要通过求解计算总和的长度 N 2 -x ＆LT; 2 ，你得到的东西像 X≈日志日志N 。

Now you only have to compute the length of the sum by solving n2-x < 2 and you get something like x ≈ log log n.

所以，解决的办法是 T（N）= O（N⋅日志日志N）。

对不起，你一直在寻找使用substitun方法的解决方案。我从来没有这样做，所以我读这个网站。

Sorry, you was looking for a solution using the substitun method. I never done this so I read a discription on this site.

让 T（开方（N））= K⋅的sqrt（N）⋅日志记录的sqrt（N）+ O（开方（N））恒氏/ code>。

Let T(sqrt(n)) = k ⋅ sqrt(n) ⋅ log log sqrt(n) + O(sqrt(n)) for constant k.

T(n) = sqrt(n) ⋅ k ⋅ sqrt(n) ⋅ log log sqrt(n) + sqrt(n) + O(sqrt(n)) 
     = k ⋅ n ⋅ log (0.5 log n) + sqrt(n) + O(sqrt(n))
     = k ⋅ n ⋅ log log n + log 0.5 + sqrt(n) + O(sqrt(n))
     = k ⋅ n ⋅ log log n + O(sqrt(n))
     = O(n log log n)

我希望这有助于。

I hope this helps.

这篇关于解决复发方程由substituion的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！