再発関係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 方程式と解決に。 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つはゼロまたはインフィニティになります。

Answer 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に置き換えられました。次に、（1）t（n）= t（（3/4）^2 * n） +2c ..............（3）にT（3N/4）を置き換えます。次に、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）

kthステップの後、eq。 t（n）= t（（3/4）^k * n）+kc ................（5）このステップnは2または1になります（5）入力サイズ）（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 3

与えられた答えは、この種の再発を解決する正しい方法を示していません。あなたのケースはaで簡単に解決されます マスター定理 そしてあなたの場合 a=1 と b=4/3. 。この意味は c = logb(a) = 0.

あなたのから f(n) 一定です、あなたは2番目のケースのバケツに落ち、どこで k=0. 。ソリューションはです , 、 どこ c = 0 と k = 0. 。この意味は：

---

O(log(n)) 正しい答えです