アルゴリズムイントロダクション Chapter 7, Chapter 6 続き

Exercise 6.5-9

リストがヒープの根からそれぞれぶらさがったヒープを作る。根っこの付近は-Infを入れておく。そのあとExtractMinを繰り返す。

Exercise 7.1-2

r
i,jの他に、kを導入。A[1..i]がpivotより小さいもの,A[i+1 .. k]がpivotと等しいもの,A[k+1 .. j]がpivotより大きいもの。

(defun Partition (A p r)
  (let ((pivot (ref A r))
	(i (1- p))
	(k (1- p)))
    (loop for j from p to (1- r)
	 if (< (ref A j) pivot) do
	   (incf i)
	   (incf k)
	   (swap (ref A j) (ref A k))
	   (swap (ref A k) (ref A i))
	 else if (= (ref A j) pivot) do
	   (incf k)
	   (swap (ref A k) (ref A j)))
    (swap (ref A (1+ k)) (ref A r))
    (truncate (/ (+ k i 2) 2))))

Exercise 7.1-3

loopが1からnまで回るので、O(n)

Exercise 7.2-1

$T(n) = \sum_{k=1}^{n} k = {\mathrm \Theta}(n^2)$

Exercise 7.2-2

${\mathrm \Theta}(n^2)$
Exercise 7.1-2のPartitionなら ${\mathrm \Theta}(n \lg n)$

Exercise 7.2-4

Quick-Sortはほとんどソートされたリストでは効率が悪い。（計算量がO(n^2）に近づく)
Insertion-Sortはほとんどソートされたリストに対して効率が良い。(計算量がO(n)に近づく)

Exercise 7.2-6

n個の配列でpivotがi番目の大きさである確率はほぼ1/nなので。（全ての要素の値が違えば厳密に1/n）

Exercise 7.3-1

漸近的な話をしているから。
nが大きくなるにつれて、実際の計算量が期待計算量に相対的に近い確率は低くならない。つまり期待計算量をTe(n),最悪計算量Tw(n)とおいて、実際の計算量T(n)が $T(n) < \frac{Te(n) + Tw(n)}{2}$ となる確率が限りなく0に近づくことはない。
さらにquicksortでは、最悪の場合と期待された場合の計算量のオーダーが違う。その場合は、上記の確率は1に近づく。

Exercise 7.3-2

最悪でも最良でも ${\mathrm \Theta}(n)$ 。
最悪:n
最良:n/2
くらいだと思う。
下の不等号が<=だった場合は厳密に全ての入力に対してn回となる。<だった場合は、Quick-Sortに長さ1の配列が渡った回数をnから引けばよい。1が出てくる回数の最大値はn/2+O(1)を超えない。

(defun Quick-Sort (A &optional (p 1) (r (len A)))
  (if (< p r) ;←この不等号;
      (let ((q (Partition A p r)))
	(Quick-Sort A p (1- q))
	(Quick-Sort A (1+ q) r)))

Exercise 7.4-5

nlg(n/k)は明らか。nkはInsertionソートで最大比較回数がkになるのでn*k。
漸近的にはk=lg nとする？
practiceではソートさせたい大きさで速い方を選ぶ？

Exercise 7.4-6

$1-6\alpha^2+4\alpha^3$
$(1 - 2\alpha)(1 + 2\alpha - 2\alpha^2)$
くらい

Problem 7-2

Exercise 7.1-2のようにする。

d

重複が無い場合より速く走ることを示せば、Exercise7.4-2とSection7.4.2から示せる。

Problem 7-3

dは積分で示したほうが直感的な気がする。

Problem 7-4

c

pivotで分割した、小さい方をスタックに積んでいく。どっちに向かってソートするかの状態を一つ増やす。

Problem 7-5

a

$\frac{6i(n-i+1)}{n^3}$

b

3/2倍

c

13/9倍

d

best-caseは変わらないので明らか

Problem 7-6

Problem 7-2のようなPartitionを使う。

	 else if (= (ref A j) pivot) do
	   (incf k)
	   (swap (ref A k) (ref A j)))

の部分を

	 else if (overlap-p (ref A j) pivot) do
	   (setf pivot (intersection (ref A j) pivot))
	   (incf k)
	   (swap (ref A k) (ref A j)))

とし、pivotを順次、aとpivotの共通部分に更新するようにする。