使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的区别
Difference between solving T(n) = 2T(n/2) + n/log n and T(n) = 4T(n/2) + n/log n using Master Method
我最近偶然发现了一个资源,其中 2T(n/2) + n/log n type 的复发被 MM 宣布为无法解决。
我接受它作为引理,直到今天,当另一个资源被证明是矛盾的(在某种意义上)。
根据资源(下面的link):其中的 Q7 和 Q18 是 rec。 1和2分别在whything的问题中,Q7的回答说不能通过给出原因'Polynomial difference b/w f(n) and n^(log a base b)'来解决。
相反,答案 18 使用案例 1 解决了第二次重复(在此处的问题中)。
http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
有人可以解惑吗?
这是因为在 Q18 中我们有 a = 4
和 b = 2
,因此我们得到 n^{log(b,a)} = n^2
其指数严格大于 [=13 的多项式部分的指数=].
如果您尝试将主定理应用于
T(n) = 2T(n/2) + n/log n
你认为 a = 2, b = 2
这意味着 logb(a) = 1
- 你能应用案例1吗?
0 < c < logb(a) = 1
。是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
,是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
。是 n/logn = O(n^0)
或 n/logn = O(n^1)
。确实 n/logn = O(n)
。因此我们有
T(n) = Theta(n^2)
注:关于0 < c <1的解释,案例1
案例 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
我最近偶然发现了一个资源,其中 2T(n/2) + n/log n type 的复发被 MM 宣布为无法解决。
我接受它作为引理,直到今天,当另一个资源被证明是矛盾的(在某种意义上)。
根据资源(下面的link):其中的 Q7 和 Q18 是 rec。 1和2分别在whything的问题中,Q7的回答说不能通过给出原因'Polynomial difference b/w f(n) and n^(log a base b)'来解决。 相反,答案 18 使用案例 1 解决了第二次重复(在此处的问题中)。
http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
有人可以解惑吗?
这是因为在 Q18 中我们有 a = 4
和 b = 2
,因此我们得到 n^{log(b,a)} = n^2
其指数严格大于 [=13 的多项式部分的指数=].
如果您尝试将主定理应用于
T(n) = 2T(n/2) + n/log n
你认为 a = 2, b = 2
这意味着 logb(a) = 1
- 你能应用案例1吗?
0 < c < logb(a) = 1
。是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
,是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
。是n/logn = O(n^0)
或n/logn = O(n^1)
。确实n/logn = O(n)
。因此我们有T(n) = Theta(n^2)
注:关于0 < c <1的解释,案例1
案例 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