この再帰関係を解こうとしています。これが私がこれまでに試みたことですが、私は間違っていると思います。いくつかのガイダンスを本当にいただければ幸いです。
これは私が解決しようとしている再帰関係です:- 2T(n^1/2) + C
T(n) = 2T(n^1/2) + C
2((2T(n^1/4)+C) + C
>> 4T(n^1/16) + 3C
>> 8T(n^1/256) + 6C
だから私はそれをこの代数式に定式化することができます:-
(2^k)T(n^(1/2^k)) + 2k
再帰関係を解くために、私は簡単に言います
n^(1/(2^k)) = 1
Therefore:- 2k = log (base n) 1
But this makes k = 0....
これは正しくないと思います。アドバイスをお願いします。喜んでお手伝いさせていただきます。
私の試み。(警告: ここで置換が正しいことかどうかはわかりません。試してみましょう。)
T(x) = 1x < 2としましょう
with T(1) はノーゴーです（私のコメントを参照）ので、おそらく T(2) を計算してみることができます
T(2) = 2 * T(sqrt(2)) + C = 2 + C
ここで、次のような k を検索します。n^(1/2^k) = 2 + C
1/(2^k) = log_n(2 + C) [base n log]
1/log_n(2 + C) = 2^k
log_(2 + C) n = 2^k [1 / log_a b = log_b a]
lg n / lg (2 + C) = 2^k [change-of-base]
c2 lg n = 2^k [since lg (2 + C) is fixed we put c2 = 1 / lg (2 + C)]
k = lg (c2 * lg n) = (lg c2) + lg lg n
k = c3 + lg lg n [since lg c2 is fixed]
ここで k を代入してT(N) = 2^k + 2k、次の式を見つけます。
T(n) = 2^c3 * lg n + 2*c3 + lg lg n
今、私たちがまとめると
T(n) = c1 lg n + c2 lg lg n
ここで、c1 と c2 は固定されており、上で使用したものとは異なります。