gpt4 book ai didi

algorithm - 使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的区别

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:32:41 27 4
gpt4 key购买 nike

我最近偶然发现了一个资源,其中 2T(n/2) + n/log n 类型 的递归被 MM 宣布为无法解决。

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

根据资源(下面的链接):其中的 Q7 和 Q18 是 rec。 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

有人可以消除困惑吗?

最佳答案

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

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/lognn^c 增长无限快
  2. 你能应用案例 2 吗?编号c = 1您需要找到一些 k > 0 使得 n/log n = Theta(n log^k n )
  3. 你能应用案例 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. 你能应用案例 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

关于algorithm - 使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28093121/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com