递归关系 T(n) = T(3/4 * n) +复杂度(1)

Question

我正在计算递推关系

T(n) = T(3/4 * n) + O(1)

它的结果是 O(log(n)) code>，但我事先被告知解决方案是O(n)。我找不到哪里出错了 - 这看起来就像二分搜索的递归关系。有什么建议吗？

Answer 1

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)

Answer 2

尝试将 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]

其中一个将收敛到一个小的正数，另一个将趋于零或无穷大。

Answer 3

给出的答案并未显示解决此类递归问题的正确方法。您的案例很容易通过 大师定理 解决，在您的案例中 a=1< /code> 和 b=4/3。这意味着c = logb(a) = 0。

因为您的 f(n) 是一个常量，所以您属于第二种情况，即 k=0。所以解决方案是 ，其中 c = 0 和 k = 0。这意味着：

---

O(log(n)) 是正确答案