- 117 名前：デフォルトの名無しさん mailto:sage [2007/06/20(水) 03:03:56 ]
- >>116
好きな人がいない場合はどうすれば良いんでしょうか?
っーか、行動半径に妙齢の女性がいないんですけれども。
話は変わって質問です。
(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乗になるのでしょうか?
|
 |
