[過去ﾛｸﾞ] 関数型言語ML (SML, OCaml, etc.), Part 6 (949ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
740(1): 2013/10/11(金)03:24 AAS
>>738
>>734の場合でも、f(n)はf(n-1), f(n-2)がメモ化されている場合常にO(1)
メモ化していない場合(最初の一回目)は再帰計算だからO(n)
これはわかるな？
その後 再帰メモ化版のfib(n)は、
それまでn以上の値が呼び出されていたならO(1)であり、
fib nをm回呼び出すならO(m)、2つ合わせて O(m+n)
アキュムレータだけの場合、fib(n)は "常に" O(n)
つまりfib nをm回呼び出すならO(nm)
わかったか？
742: 2013/10/11(金)10:20 AAS
>>740
あー >>734はメモ化の再帰ﾊﾞｰｼﾞｮﾝの話ね
理解した
とすると
>>729この違いは
使い捨てならアキュムバージョンは
簡潔に書けて早く
使いまわすならメモ化した方が
再呼び出しは早くていいって感じか
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.028s