复发关系t（n）= t（3/4 * n） + o（1）

Question

我正在锻炼复发关系

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

它是 O(log(n)), ，但事先我被告知解决方案是 O(n). 。我找不到我要在哪里出错的地方 - 这看起来像是二进制搜索的复发关系。有什么建议么？

Answer 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]

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

Answer 2

t（n）= t（3/4 * n） + o（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 ..................................................................................................................................................

在KTH步骤等式之后。将为t（n）= t（（3/4）^k * n）+kc .....................................................................................................................................输入大小）（3/4）^k * n = 1 n =（4/3）^k，通过在两侧进行登录。 log(n)=k*log(4/3) k=log(n) .............. place value in eq. (5) T(n)=T(1)+log(n) * c ..............(6) T(n)= O(log n)

Answer 3

给出的答案并未显示出解决此类复发的正确方法。您的情况很容易解决 大师定理 在你的情况下 a=1 和 b=4/3. 。这意味着 c = logb(a) = 0.

因为你 f(n) 是一个常数，您属于第二个情况桶，哪里 k=0. 。因此解决方案是 , ， 在哪里 c = 0 和 k = 0. 。这意味着：

---

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