【O(n)】計算量の評価方法について【O(log n)】at TECH【O(n)】計算量の評価方法について【O(log n)】 - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このｽﾚｯﾄﾞのURL■項目テキスト63:デフォルトの名無しさん 16/08/07 17:01:40.20 sg2m+nAp.net >>57 64:デフォルトの名無しさん 16/08/26 15:22:07.02 4Tk0fahk.net 開平・開立のアルゴリズムって最速なのdeath？ 65:デフォルトの名無しさん 17/01/08 21:33:16.56 5b4VWoeT.net F(p, n, r) の計算量を教えてください。 n: 整数 p, r: 整数配列（インデックス0からn-1） F(p, n, r): if r[n] ≧ 0: return r[n] if n == 0: q = 0 else: q = -∞, for i = 1 to n: q = max(q, p[i] + F(p, n-i, r)) return r[n] = q 66:デフォルトの名無しさん 17/01/08 21:33:49.00 5b4VWoeT.net T(n) = c1 + c2 * n + T(n-1) + … + T(0) = c1 + c2 * n + T(n-1) + c3*(n-1) と解けばいいんですかね？ 67:デフォルトの名無しさん 17/01/08 21:34:12.25 5b4VWoeT.net T(n) = c1 + c2*n + T(n-1) T(0) = c3 この漸化式の解を求めればいいんですかね？ 68:デフォルトの名無しさん 17/01/08 21:34:50.14 5b4VWoeT.net T(n) = [T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0) = [c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3 = c1*n + c2*(1/2)*n*(n+1) + c3 = Θ(n^2) 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch