ログイン

お使いのブラウザ(Internet Explorer)では閲覧、ログイン、質問の作成や回答などに不具合が生じることがございます。
誠に恐れ入りますが、下記の推奨ブラウザをご利用くださいませ。

推奨ブラウザ:Google Chrome(グーグル・クローム)

勉強レベル1

logと関数に関しての漸化式の証明問題

【質問の答えについて】

この質問の答えはわかりません。

logと関数に関しての漸化式の証明問題です。

以下の問題についてどのように考えればいいか、検討がつかず困っています。


a >0, b>1, d>=0, n= b^k(kは自然数), Lは定数


p(n) = L (n=1のとき)


p(n) = a*p(n/b) + L * n^d (n>=2のとき)


が成り立っている


このとき以下を示せ


p(n) = O(n^d)(d >logbaのとき)


p(n)  = O((n^d )*logn) (d =logbaのとき)


p(n)  =O (n^(logba)) (d <logbaのとき)


ただし、logba は底がbで真数はa


O()は時間計算量を示す
0回答一覧

質問する

回答する場合は ログイン が必要です。
  • この回答を見た人は以下の回答も見ています