アルゴリズムイントロダクション 2 章「本書の枠組みについて」
数学的基礎とデータ構造 (アルゴリズムイントロダクション)の 2章
2.1-1
- (<31> 41 59 26 41 58)
- (<31 41> 59 26 41 58)
- (<31 41 59> 26 41 58)
- (<26 31 41 59> 41 58)
- (<26 31 41 43 59> 58)
- (<26 31 41 43 58 59>)
2.1-2
不等号を逆に。
2.1-3
LINEAR-SEARCH(A, v) 1. for i <- 1 to length[A] 2. do val <- A[i] 3. if val = v then 4. return i 5. end 6. return nil
- ループ不変式は「部分配列[j - 1] までに v が存在せず、v が存在するならば [j] 以降にあること。
- 初期条件：部分配列は空なので v が存在しない事は明らか
- ループ内条件：[j - 1] までの部分配列に存在していれば return しているはずなので成り立つ。
- 終了条件：v が見つかったときには i が returnされ、そうでないときは必ず nil が return される。
2.1-4
ADD-2bit(A, B) 1. for i <- length[A] to 1 2. do valA <- A[i], valB <- B[i] 3. if val = v then 4. return i 5. end 6. return nil
2.2-1
\Theta(n^3)
2.2-2
SELECTION-SORT(A) 1. for i <- 2 to length[A] 2. minIdx = i 3. for j <- i to length[A] 4. if A[j] < A[minIdx] 5. minIdx = j 6. end 7. end 8. swap(A, i, minIdx) 9. end
- 不変式:ループの途中で左側はソート済み。右側には左側にある要素より大きな要素はない。
- n - 1 なのは n = 1 のときに
- 最良・最悪の場合ともに \Theta(n^2)
2.2-3
- 等確率なら N/2
- 最悪は N
- \Theta(N)
2.2-4
問題の意図が分からないが、定数係数を小さくするように計算資源を増やすとか。
それとも特別な場合かどうかチェックして計算済みの物を返すとか。
2.3-1
<3 9 26 38 41 49 52 57><3 26 41 52> <9 38 49 57><3 41> <26 52> <38 57> <9 49><3> <41> <52> <26> <38> <57> <9> <49>
2.3-2
if i = n1
then
copy(A, k, R)
return;
else
if j = n2
then
copy(A, k, L)
return;
else
....
2.3-3
k = 1 (n = 2)のとき T(2) = 2 = 2 * lg(2) だから成り立つ 任意の n = 2^k に関して成り立つと仮定すると T(2^k) = 2^k * lg(2^k) = k * 2^k (a) が成り立つ。 T(2^(k + 1)) = 2T(2^k) + 2^(k + 1) = 2 * k * 2^k + 2^(k + 1) // (a) を利用 = (k + 1) * 2^(k + 1) となり k + 1 でも成り立つ。
2.3-4
T(n) = 1 (n=1のとき)
T(n) = T(n - 1) + n
2.3-5
BINARY_SEARCH(A, L, U, v) 1. if L == U 2. then 3. return nil; 4. else 5. m = (L + U)/2 6. if A[m] == v 7. then 8. return m; 9. else if A[m] > v 10. then 11. return BINARY_SEARCH(A, L, m, v) 12. else 13. return BINARY_SEARCH(A, m, U, v)
最悪は見つからない場合。log2(n) 回比較が行われる。
2.3.6
できない。挿入する場所は lg(n) で見つかるがずらす作業が必要。
数学的基礎とデータ構造 (アルゴリズムイントロダクション)
posted with amazlet at 09.12.06
