recursion - 再帰関係 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) = 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 に置き換え. (1) に T(3n/4) を代入します 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番目のステップの式の後。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*norT(n) = c * log nを方程式に代入して解いてみてください。2 つの方程式のうちの 1 つが解けるようになります。

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]

これらのうちの 1 つは小さな正の数に収束し、もう 1 つはゼロまたは無限大になります。