1

我只是想验证一些事情我是否执行了以下步骤？

T(n)   = 3T(n/3) + n  : Theta(nlogn)

O(nlogn)

T(k)   = cklog(k)  k<n

T(n/4) = c(n/3)log(n/3)
       = c(n/3)[logn - log3]
       = c(n/3)logn - c(n/3)log3    

T(n)   = cnlogn-cnlog3 + n

       <= cnlogn -cn + n 
       <= cnlogn -dn **[STEP A]**
       <= cnlogn if c >= d

Omega(nlogn)
   >= cnlogn -cn + n 
   >= cnlogn -dn **[STEP A]**
   >= cnlogn if 0 < c <= d

我在步骤 A 中遇到了问题，我最终的 c 范围是：

c >= 1 表示上限 0 < c <= 1 表示下限

将 cn + n 结合起来有什么特殊原因吗？我可以看到它背后的逻辑，但有必要做那一步吗？因为那样我可以在任何情况下都这样做......这有点奇怪......

4

1 回答 1

1

你仍然是对的，直到：

T(n) = cnlogn-cnlog3 + n
     >= cnlogn -cn + n

为了Ω(nlogn)

因为它只适用于 c <= 0，这与我们假设 c >= 0 相矛盾。

修复第二个证明的一种方法可能是：

T(n) = cnlogn - cnlog3 + n
     = cnlogn - n(clog3 - 1)
     <= cnlogn when c >= 1/log3

因此：T(n) = Ω(nlogn)。

通常，下限和上限的值并不重要。目标是找到两个常数c1，c2这样：

c1*n*logn <= T(n) <= c2*n*logn全部n >= some n0。

于 2012-03-03T20:33:43.910 回答