我最近偶然发现了一个资源，其中 2T(n/2) + n/log ntypeMM 宣布复发无法解决。
我接受它作为一个引理，直到今天，另一种资源被证明是矛盾的（在某种意义上）。
根据资源（下面的链接）：其中的 Q7 和 Q18 是建议。分别在问题中的1和2中，Q7的答案说不能通过给出原因“多项式差b/w f(n)和n^(log a base b)”来解决。
相反，答案 18 使用案例 1 解决了第二个递归问题（在此问题中）。
http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
有人可以消除困惑吗？
如果你尝试将主定理应用到
T(n) = 2T(n/2) + n/log n
你考虑a = 2, b = 2意思是logb(a) = 1
- 可以应用案例1吗？
0 < c < logb(a) = 1. Is n/logn = O(n^c)。没有为什么n/logn增长速度无限快于n^c
- 可以应用案例2吗？不。
c = 1你需要找到一些k > 0这样n/log n = Theta(n log^k n )
- 可以应用案例3吗？
c > 1, is n/logn = Big Omega(n^c)？不，因为它甚至不是Big Omega(n)
如果你尝试将主定理应用到
T(n) = 4T(n/2) + n/log n
你考虑a = 4, b = 2意思是logb(a) = 2
-
可以应用案例1吗？c < logb(a) = 2. is n/logn = O(n^0) or n/logn = O(n^1)。确实是的n/logn = O(n)。因此我们有
T(n) = Theta(n^2)
注意：关于 0
案例 1 更多的是关于分析。
f(x) = x/log(x) , g(x) = x^c , 0< c < 1
f(x) is O(g(x)) if f(x) < M g(x) after some x0, for some M finite, so
f(x) is O(g(x)) if f(x)/g(x) < M cause we know they are positive
这在这里不是真的 我们摆姿势y = log x
f2(y) = e^y/y , g2(y) = e^cy , 0< c < 1
f2(y)/g2(y) = (e^y/y) / (e^cy) = e^(1-c)y / y , 0< c < 1
lim inf f2(y)/g2(y) = inf
lim inf f(x)/g(x) = inf
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
