[ ホームページ ] [ 携帯用URL ]
DS 数学 BBS・2
小中高の範囲は DS 数学 BBS(携帯電話用)へ。
数学以外の話題は赤猫雑談掲示板で。
注意事項, 記号の書き方例をお読みになった上でご利用ください。

[ EZBBS.NET | 新規作成 | ランキング | オプション ]
iモード&(絵文字)、au対応!ケータイからも返信できる無料掲示板!
名前
 E-mail 
題名
内容

投稿KEY    タグ有効 改行有効 等幅フォント
URL
 
掲示板のTOP | 過去ログ集 | 投稿練習 | よく質問される問題 | エッセイblog



60338.logと関数に関しての漸化式の証明問題  
名前:はる    日付:2019年05月14日(火) 23時28分
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()は時間計算量を示す
p3629233-ipngnfx01hodogaya.kanagawa.ocn.ne.jp (123.226.228.233)
Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/74.0.3729.131 Safari/537.36


「60338.logと関数に関しての漸化式の証明問題」への返信

無料アクセス解析

アクセス解析の決定版!無料レンタルで最大100ページ解析!

特定の個人への誹謗中傷は無予告削除対象です。
   投稿KEY
   パスワード

EZBBS.NET produced by InsideWeb