【入門】Common Lisp その3【質問よろず】
■ このスレッドは過去ログ倉庫に格納されています
0117デフォルトの名無しさん
2007/06/20(水) 03:03:56好きな人がいない場合はどうすれば良いんでしょうか?
っーか、行動半径に妙齢の女性がいないんですけれども。
話は変わって質問です。
(defun reverse$ (lst)
(if (null lst) nil
(append (reverse$ (rest lst))
(list (first lst)))))
でリストの長さnがある程度長いとするとreverse$の計算時間がnの2乗に
比例すると本に書いてあって、
時間をT(n)として、
(rest lst)の長さは
n-1なので(reverse$ (rest lst))の計算時間はT(n-1),
(list (first lst))の時間は1,appendの時間はn-1となる。
T(0)=1とみなすと、
T(n)=T(0)+1+2+......+n=(n^2+n+2)/2,n=0,1,.....
と説明してあるのですが、いまいちピンと来ません。
どうしてこのreverse$の計算時間がリストの長さの2乗になるのでしょうか?
■ このスレッドは過去ログ倉庫に格納されています