我正在计算递归关系
T(n) = T(3/4 * n) + O(1)
它出来了O(log(n))，但我事先被告知解决方案是O(n)。我找不到哪里出错了——这看起来就像二分搜索的递归关系。有什么建议么？
问问题
3553 次
3 回答
2
T(n) = T(3/4 * n) + O(1) ......(1) 在上面的等式中。T(3/4 * n) 是未知项，如果你问这个递归的解决方案，那么我想说我们可以解决这个方程。使用替代方法。在此我们必须从主方程中找出 T(3n/4) 的值。并在等式中替换。递归地。因为这种递归取决于递归。n=3n/4 T(3n/4)=T((3/4)^2 * n)+ c .............(2) 符号 O 由常数 c 代替. 现在将 T(3n/4) 替换为 (1) T(n)= T((3/4)^2 * n) +2c ................(3)现在将 n=((3/4)^2 * n) 放入 (1) T((3/4)^2 * n)=T((3/4)^3 * n)+c 代入 T(n )= T((3/4)^3 * n)+3c ......(4)
在第 k 步 eq 之后。将是 T(n)=T((3/4)^k * n)+kc ......(5) 在这一步 n 将是 2 或 1(输入大小) (3/4)^k * n= 1 n=(4/3)^k 通过在两边取日志。log(n)=k*log(4/3) k=log(n) ....... 将值放入等式。(5) T(n)=T(1)+log(n) * c ........(6) T(n)= O(log n)
于 2011-02-08T05:14:12.180 回答
1
尝试将T(n) = c*n或代T(n) = c * log n入方程并求解。这两个方程之一将是可解的。
您还可以通过评估不同 n 值的函数来检查您的答案。
-- Define T in your preferred language
t n | n <= 1 = 1 | otherwise = t (3/4 * n) + 1
-- If it's O(log n), then T(n)/log(n) should be asymptotically constant
-- If it's O(n), then T(n)/n should be asymptotically constant
check1 n = t n / log n
check2 n = t n / n
print [check1 1e10, check1 1e11, check1 1e12, check1 1e13]
print [check2 1e10, check2 1e11, check2 1e12, check2 1e13]
其中一个将收敛到一个小的正数，另一个将趋于零或无穷大。
于 2010-12-05T19:10:54.567 回答
0
给出的答案没有显示解决这种重复的正确方法。你的情况很容易用Masters 定理解决，在你的情况下a=1和b=4/3. 这意味着c = logb(a) = 0.
因为你f(n)是一个常数，所以你落入第二种情况的桶和哪里k=0。所以解决方案是
， wherec = 0和k = 0。这意味着：
O(log(n))是正确答案
于 2015-12-13T09:17:56.963 回答