再発関係t(n)= t(3/4 * n) + o(1)
-
08-10-2019 - |
質問
私は再発関係を取り上げています
T(n) = T(3/4 * n) + O(1)
それは出てきています O(log(n))
, 、しかし、私は解決策は O(n)
. 。私はどこで間違っているのかを見つけることができません - これはバイナリ検索の再発関係のように見えます。助言がありますか?
解決
置換を試してみてください 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つはゼロまたはインフィニティになります。
他のヒント
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)
与えられた答えは、この種の再発を解決する正しい方法を示していません。あなたのケースはaで簡単に解決されます マスター定理 そしてあなたの場合 a=1
と b=4/3
. 。この意味は c = logb(a) = 0
.
あなたのから f(n)
一定です、あなたは2番目のケースのバケツに落ち、どこで k=0
. 。ソリューションはです , 、 どこ c = 0
と k = 0
. 。この意味は:
O(log(n))
正しい答えです