使用主方法求解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

问题描述

我最近偶然发现一种资源，MM宣布无法解决2T（n / 2）+ n / log n 类型的复发。

I recently stumbled upon a resource where the 2T(n/2) + n/log n type of recurrences were declared unsolvable by MM.

直到今天，当证明另一种资源（在某种意义上是矛盾的）时，我才接受它作为引理。

I accepted it as a lemma, until today, when another resource proved to be a contradiction (in some sense).

根据资源（以下链接） ：其中的Q7和Q18是记录。问题7的答案分别是1和2，因此问题7的答案说不能通过给出原因多项式差b / w f（n）和n ^（log a base b）来解决。
相反，答案18使用情况1解决了第二次重现（在这里的问题中）。

As per the resource (link below): Q7 and Q18 in it are the rec. 1 and 2 respectively in the question whereby, the answer to Q7 says it can't be solved by giving the reason 'Polynomial difference b/w f(n) and n^(log a base b)'. On the contrary, answer 18 solves the second recurrence (in the question here) using case 1.

http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf

有人可以消除混乱吗？

推荐答案

如果您尝试将主定理应用于

If you try to apply the master theorem to

T(n) = 2T(n/2) + n/log n

您考虑 a = 2，b = 2 这意味着 logb（a）= 1

1. 您可以应用案例1吗？ 0< c ＜ logb（a）= 1 。是 n / logn = O（n ^ c）。不，因为 n / logn 的增长无限快于 n ^ c


2. 您可以申请案例2吗？否。 c = 1 您需要找到一些 k> 0 ，以使 n / log n = Theta（n log ^ kn）


3. 可以应用案例3吗？ c> 1 ，是 n / logn = Big Omega（n ^ c）吗？不，因为它甚至不是 Big Omega（n）

1. Can you apply case 1?0 < c < logb(a) = 1. Is n/logn = O(n^c). No, because n/logn grow infinitely faster than n^c
2. Can you apply case 2? No. c = 1 You need to find some k > 0 such that n/log n = Theta(n log^k n )
3. Can you apply case 3 ? c > 1, is n/logn = Big Omega(n^c) ? No because it is not even Big Omega(n)

如果您尝试将主定理应用于

If you try to apply the master theorem to

T(n) = 4T(n/2) + n/log n

您考虑 a = 4，b = 2 ，这意味着 logb（a）= 2

1. 可以应用案例1吗？ c< logb（a）= 2 。是 n / logn = O（n ^ 0）或 n / logn = O（n ^ 1）。是的，确实 n / logn = O（n）。因此，我们有

1. Can you apply case 1? c < logb(a) = 2. is n/logn = O(n^0) or n/logn = O(n^1). Yes indeed n/logn = O(n). Thus we have

T(n) = Theta(n^2)

注意：有关0的解释c< 1，案例1

note: Explanation about 0 < c <1, case 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

This isnt true here We pose 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

这篇关于使用主方法求解T（n）= 2T（n / 2）+ n / log n和T（n）= 4T（n / 2）+ n / log n之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！