[過去ﾛｸﾞ] 関数型言語ML (SML, OCaml, etc.), Part 6 (949ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
738(2): 2013/10/11(金)01:37 AAS
>>734この
二重再帰の計算オーダーはそうじゃないだろ？？
739: 2013/10/11(金)02:57 AAS
>>735
>>738
メモ化のコード書いてくれないとわからない。
あと計算オーダーはそうじゃないのそうって何？
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)
わかったか？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.032s