[過去ﾛｸﾞ] 関数型言語ML (SML, OCaml, etc.), Part 6 (1002ﾚｽ)

関数型言語ML (SML, OCaml, etc.), Part 6 http://mevius.5ch.net/test/read.cgi/tech/1245017721/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

734: デフォルトの名無しさん [sage] 2013/10/10(木) 19:24:41.41 fib(n) = fib(n-1) + fib(n-2) fib(n-2)は呼ばれるが、計算済みだから新に計算はしないってことでしょ。 http://mevius.5ch.net/test/read.cgi/tech/1245017721/734

738: デフォルトの名無しさん [] 2013/10/11(金) 01:37:05.82 >>734この 二重再帰の計算オーダーはそうじゃないだろ？？ http://mevius.5ch.net/test/read.cgi/tech/1245017721/738

740: デフォルトの名無しさん [sage] 2013/10/11(金) 03:24:27.66 >>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) わかったか？ http://mevius.5ch.net/test/read.cgi/tech/1245017721/740

742: デフォルトの名無しさん [] 2013/10/11(金) 10:20:41.62 >>740 あー　>>734はメモ化の再帰ﾊﾞｰｼﾞｮﾝの話ね 理解した とすると >>729この違いは 使い捨てならアキュムバージョンは 簡潔に書けて早く 使いまわすならメモ化した方が 再呼び出しは早くていいって感じか http://mevius.5ch.net/test/read.cgi/tech/1245017721/742

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.030s