Comment on page
アルゴリズムイントロダクション

概要
本
​アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書) | T. コルメン, R. リベスト, C. シュタイン, C. ライザーソン, Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 浅野 哲夫, 岩野 和生, 梅尾 博司, 山下 雅史, 和田 幸一​
参考
​Introduction to Algorithms, Third Edition | The MIT Press​
​演習問題の解答​
公式の解答。一部の問題のみ、解答が記載されている
かかった時間
x 時間
読む前の状態
xxx
進め方
演習問題は解いていない
感想
xxx
読書メモ
Ⅰ: 基礎
1. 計算におけるアルゴリズムの役割
アルゴリズムは、ある値または値の集合を入力(input)として取り、ある値または値の集合を出力(output)として生成する、明確に定義された計算手続き
データ構造は、アクセスと更新を容易にする目的のために、データを蓄積し組織化する方法
どのデータ構造もすべての目的に対して満足に働くことはない。したがって、いくつかのデータ構造について、その長所と限界を理解することが重要
2. さあ、始めよう
挿入ソート(insertion sort)
トランプの手札をソートするようなイメージ
左手を空にし、テーブルの上にカードを裏向きに置く
テーブルから 1 枚ずつカードを取って、左手の正しい位置に挿入していく
for j = 2 to A.length
  key = A[j]
  // A[j]をソート済みの列A[1..j-1]に挿入する
  i = j - 1
  while i > 0 かつ A[i] > key
    A[i + 1] = A[i]
    i = i - 1
  A[i + 1] = key
ループ不変式(loop invariant)
簡単に言うと、ループの全ての反復に対して、保持される条件
厳密に言うと以下の 3 つの性質がある
初期条件
ループの実行開始直前で、ループ不変式は真
ループ内条件
ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真である
終了条件
ループが停止した時、アルゴリズムの正当性の証明につながる有力な性質が不変式から得られる
アルゴリズムの解析
アルゴリズムの実行に必要な資源量を予測することを、アルゴリズムを解析する(analyzing)という
多くの場合、測定したいのは計算時間
アルゴリズムを解析するには、使用する実現技術のモデルを設定する必要がある。このモデルには実現技術で用いられる資源とそのコストのモデルが含まれる
本書では、基本的な単一プロセッサの計算モデルであるランダムアクセスマシン(RAM)を実現技術として仮定し、アルゴリズムは計算機プログラムとして実現する
RAM モデルでは命令は 1 つずつ逐次的に実行され、並列演算は存在しない
実行時間
ある特定の入力に対するアルゴリズムの実行時間(running time)は、実行される基本演算または「ステップ」の数
最悪時と平均時の解析
本書では通常の場合、最悪実行時間(worst-case running time)だけを考える
以下の 3 つが理由
実行時間の上界を知ることで、アルゴリズムの実行にそれ以上の時間がかからないことを保証できる
あるアルゴリズムでは、最悪の場合がかなり頻繁に生ずることがある
平均的な場合が、最悪の場合と同じくらい悪いことが多い
増加のオーダ(order of growth)
実行時間の増加率が重要
例えば挿入ソートだと θ(n^2) となる
分割統治法(devide-and-conquer)
再帰構造を持つアルゴリズムは、多くの場合、分割統治法に基づいて設計されている
分割統治パラダイムの再帰の各レベルは以下の 3 つの段階から構成される
分割
問題をいくつかの同じ問題のより小さいインスタンスである部分問題に分割する
統治
部分問題を再帰的に解くことによって統治する。ただし、部分問題のサイズが十分小さい場合は直接的な方法で解く
結合
部分問題の解を組み合わせて元の問題の解を得る
マージソート(merge sort)
MERGE-SORT(A, p, r)
if p < r
  q = [(p + r) / 2]
  MERGE-SORT(A, p, q)
  MERGE-SORT(A, q + 1, r)
  MERGE(A, p, q, r)
​
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
// L[1..n1+1] と R[1..n2+1] を2つの新しい配列とする
for i = 1 to n1
  L[i] = A[p + i - 1]
for j = 1 to n2
  R[i] = A[q + j]
L[n1 + 1] = ∞
R[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
  if L[i] <= R[j]
    A[k] = L[i]
    i = i + 1
  else
    A[k] = R[j]
    j = j + 1
分割統治アルゴリズムの解析
問題を a 個の部分問題に分割され、各部分問題のサイズは元の問題の 1/b であるとする
また問題を部分問題に分割するのに D(n) 時間かかり、部分問題の解を結合するのに C(n) 時間かかるとする
以下の漸化式で表せる
T = θ(1) (n <= c の時)
T = aT(n/b) + D(n) + C(n) (それ以外の時)
このような形式の漸化式を解く方法は 4 章で学ぶ
マージソートの場合は θ(nlgn)
3: 関数の増加
θ記法(θ-notation)
定義
ある与えられた関数 g(n) に対して、θ(g(n)) を以下のように定義する
θ(g(n)) = {f(n): ある正の定数 c1, c2, n0 が存在して、すべての n >= n0 に対して 0 <= c1g(n) <= f(n) <= c2g(n) を満たす}
上記の時、g(n) は f(n) の漸近的にタイトな限界(asymptotically tight bound)という
Ｏ記法(Ｏ-notation、ビッグオーまたはオー)
θ記法は関数を漸近的に上下から限定する。漸近的上界(asymptotic upper bound)だけに関心がある時はＯ記法を用いる
定義
Ｏ(g(n)) = {f(n): ある正の定数 c, n0 が存在して、すべての n >= n0 に対して 0 <= f(n) <= cg(n) を満たす}
Ω記法(Ω-notation、ビッグオメガまたはオメガ)
Ｏ記法が関数の漸近的上界を与えるのに対し、Ω記法は漸近的下界(asymptotically lower bound)を与える
定義
Ω(g(n)) = {f(n): ある正の定数 c, n0 が存在して、すべての n >= n0 に対して 0 <= cg(n) <= f(n) を満たす}
o 記法(o-notation、リトルオー)
漸近的にタイトでない上界を表すのに o 記法を用いる
定義
o(g(n)) = {f(n): 任意の正の定数 c > 0 に対して、ある正の定数 n0 > 0 が存在して、すべての n >= n0 に対して 0 <= f(n) < cg(n) を満たす}
ω記法(ω-notation、リトルオメガ)
漸近的にタイトでない下界を表すのにω記法を用いる
定義
ω(g(n)) = {f(n): 任意の正の定数 c > 0 に対して、ある正の定数 n0 > 0 が存在して、すべての n >= n0 に対して 0 <= cg(n) < f(n) を満たす}
関数の比較
推移性
f(n) = θ(g(n)) かつ g(n) = θ(h(n)) ならば f(n) = θ(h(n))
f(n) = Ｏ(g(n)) かつ g(n) = Ｏ(h(n)) ならば f(n) = Ｏ(h(n))
f(n) = Ω(g(n)) かつ g(n) = Ω(h(n)) ならば f(n) = Ω(h(n))
f(n) = o(g(n)) かつ g(n) = o(h(n)) ならば f(n) = o(h(n))
f(n) = ω(g(n)) かつ g(n) = ω(h(n)) ならば f(n) = ω(h(n))
反射性
f(n) = θ(f(n))
f(n) = Ｏ(f(n))
f(n) = Ω(f(n))
対称性
f(n) = θ(g(n)) の時、かつその時に限り g(n) = θ(f(n))
転置対称性
f(n) = Ｏ(g(n)) の時、かつその時に限り g(n) = Ω(f(n))
f(n) = o(g(n)) の時、かつその時に限り g(n) = ω(f(n))
4: 分割統治
漸化式(recurrence)
漸化式はある入力に対する関数値を、それより小さい入力に対する関数値を用いて記述する等式または不等式である
漸化式を解く方法 3 つ
置換え法(substitution method)
まず限界を推測し、次にその推測が正しいことを数学的帰納法を用いて証明する
再帰木法(recursion-tree method)
節点が再帰の各レベルで必要なコストを表現する木の形に漸化式を変形し、和を上または下から抑える技法を用いて漸化式を解く
マスター法(master method)
定数 a >= 1、b >= 1 と与えられた関数 f(n) によって T(n) = a*T(n/b) + f(n) と表現できる漸化式に対する限界を与える
最大部分配列問題
配列 A に対して、要素の和を最大化する A の連続する部分配列を発見する問題
この連続する部分配列を最大部分配列(maximum subarray)と呼ぶ
分割統治による解
部分配列の中央点 mid を計算し、部分配列 A[low ... mid] と A[mid+1 ... high] を考察する。すると、最大部分配列 A[i ... j] が見つかるのは以下の 3 つのどこかになる
完全に部分配列 A[low ... mid] の中にある。従って low <= i <= j <= mid
完全に部分配列 A[mid+1 ... high] の中にある。従って mid + 1 <= i <= j <= high
中央点をまたいでいる。従って low <= i <= mid < j <= high
FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low
  return (low, high, A[low]) // 基底。要素数1
else mid = (low + high) / 2
  (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
  (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid + 1, high)
  (cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
if left-sum >= right-sum and left-sum >= cross-sum
  return (left-low, left-high, left-sum)
else if right-sum >= left-sum and right-sum >= cross-sum
  return (right-low, right-high, right-sum)
else
  return (cross-low, cross-high, cross-sum)
​
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -∞
sum = 0
for i = mid downto low
  sum = sum + A[i]
  if sum > left-sum
    left-sum = sum
    max-left = i
right-sum = -∞
sum = 0
for j = mid + 1 to high
  sum = sum + A[j]
  if sum > right-sum
    right-sum = sum
    max-right = i
return (max-left, max-right, left-sum + right-sum)
行列積
単純な分割統治
以下を利用する
C11 = A11 * B11 + A12 * B21
C12 = A11 * B12 + A12 * B22
C21 = A21 * B11 + A22 * B21
C22 = A21 * B12 + A22 * B22
n/2 * n/2 型行列の積の計算は T(n/2) 時間かかる
加算にはそれぞれ θ(n^2) 時間かかる
以上から
T(n) = θ(1) n = 1 の時
T(n) = 8T(n/2) + θ(n^2) n > 1 の時
SQUARE-MATRIX-MULTIPLY-RECURSIVE
n = A.rows
// C を新しい n * n 型行列とする
if n == 1
  c11 = a11 * b11
else
  C11 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B21)
  C12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B22)
  C21 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B11) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B21)
  C22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B22)
return C
Strassen の方法
8 回あった n/2 * n/2 型行列の計算を 7 回で済ませる
10 個の n/2 * n/2 型行列 S1, S2,..., S10 を生成し、7 個の行列積 P1, P2,..., P7 を再帰的に計算する
すると Strassen のアルゴリズムの実行時間 T(n) は以下のようになる
T(n) = θ(1) n = 1 の時
T(n) = 7T(n/2) + θ(n^2) n > 1 の時
置換え法(substitution method)
2 段階で漸化式を解く
解の形を推定する
数学的帰納法を用いて定数を求め、推定した解がうまく働くことを示す
解の正しさを簡潔に証明するのに適しているが、うまい解の推定に苦労することがある
再帰木法(recursion tree)
再帰木では、各節点はある再帰関数呼び出しに対応する部分問題のコストを表す
再帰木の各レベルにおいて、そのレベルに属する節点のコストの総和を取ることでレベルごとのコストを求め、レベルごとのコストの総和を取ることで再帰木全体のコストを求める
再帰木はいい推定を得るための最適の道具。そして得た推定の正しさを置換え法によって検証する
漸化式を解くためのマスター法
a >= 1 と b > 1 を定数、f(n) を関数とする。非負整数上の関数 T(n) を漸化式 T(n) = a * T(n/b) + f(n) によって定義する。すると T(n) は漸近的に次の限界を持つ
ある定数 ε > 0 に対して f(n) = Ｏ(n^logb a-ε) ならば、T(n) = θ(n^logb a)
f(n) = θ(n^logb a) ならば、T(n) = θ(n^logb a * lg n)
ある定数 ε > 0 に対して f(n) = Ω(n^logb a+ε) であり、しかもある定数 c < 1 と十分大きな全ての n に対して a * f(n/b) <= c * f(n) ならば、T(n) = θ(f(n))
5: 確率的解析と乱択アルゴリズム
確率的解析(probabilistic analysis)
確率を用いる問題の解析を確率的解析という
乱択アルゴリズム(randomized algorithm)
一般的に、アルゴリズムの振る舞いが入力と乱数生成器(random-number generator)が生成する値の両方によって決まる時、このアルゴリズムを乱択アルゴリズムと呼ぶ
期待実行時間(expected running time)
乱択アルゴリズムの実行時間を解析する時には、乱数生成器が返す値の分布の上で実行時間の期待値を取る
乱択アルゴリズムの実行時間を期待実行時間と呼ぶ
PERMUTE-BY-SORTING
多くの乱択アルゴリズムでは、与えられた入力配列を置換することで入力をランダム化する。PERMUTE-BY-SORTING はこのやり方の 1 つ。あとでもう 1 つの RANDOMIZE-IN-PLACE を紹介する
PERMUTE-BY-SORTING は配列の各要素 A[i] に対してランダムに優先度 P[i] を割り当て、A の要素を優先度に従ってソートするやり方
マージソートに θ(n * lg n) 時間かかるので、このやり方は Ω(n * lg n) 時間かかる
PERMUTE-BY-SORTING(A)
n = A.length
P[1..n] を新しい配列とする
for i = 1 to n
  P[i] = RANDOM(1, n^3) // 1 から n^3 の間で乱数を選ぶ
P をキーとして A をソートする
RANDOMIZE-IN-PLACE
これは Ｏ(n) 時間で実現でき、PERMUTE-BY-SORTING より速い
RANDOMIZE-IN-PLACE(A)
n = A.length
for i = 1 to n
  A[i] と A[RANDOM(i, n)] を置き換える
Ⅱ: ソートと順序統計量
6: ヒープソート
ヒープ(heap)
(2 分木)ヒープデータ構造は、おおよそ完全 2 分木と見なすことができる配列オブジェクト
ヒープを表現する配列は 2 つの属性を持つ
A.length は通常通り配列の要素数を表す
A.heap-size は配列 A に格納されているヒープの要素数を表す
max ヒープと min ヒープ
max ヒープ
根以外の任意の節点 i が A[Parent(i)] >= A[i] の max ヒープ条件を満たすもの
min ヒープ
根以外の任意の節点 i が A[Parent(i)] <= A[i] の max ヒープ条件を満たすもの
高さ
ヒープを木とみなした時、ヒープにおける節点の高さを、その節点からある葉に下る最長の単純パスに含まれる変数と定義する
ヒープの高さは、その根の高さと定義する
n 個の要素を含むヒープの高さは完全二分木に基づいているので θ(lg n) である
ヒープ条件の維持
max ヒープ条件を維持するために手続き MAX-HEAPIFY を呼び出す
入れ替える対象となるどちらの子の部分木のサイズも 2n/3 以下だから（最悪の場合、は木の最ものレベルがちょうど半分だけ埋まっている時に起こる）、MAX-HEAPIFY の実行時間は漸化式 T(n) <= T(2n/3) + θ(1) で表現できる
計算すると T(n) = Ｏ(lg n) である
MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l <= A.heap-size かつ A[l] > A[i]
  largest = l
else
  largest = i
if r <= A.heap-size かつ A[r] > A[largest]
  largest = r
if largest != i
  A[i] を A[largest] と交換する
  MAX-HEAPIFY(A, largest)
ヒープの構築
ボトムアップ的に手続き MAX-HEAPIFY を適用することで、配列 A[1..n] を max ヒープに変換できる
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = A.length/2 downto 1
  MAX-HEAPIFY(A, i)
ヒープソートアルゴリズム
最初に max ヒープを構築し、そこから順々に最大要素を取り出していく
実行時間は Ｏ(n * lg n)
実行時間 Ｏ(lg n) の MAX-HEAPIFY が n - 1 回呼ばれる
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
  A[1] を A[i] と交換する
  A.heap-size = A.heap-size - 1
  MAX-HEAPIFY(A, 1)
7: クイックソート
クイックソート(quick sort)
分割統治法の 3 つの段階を以下に示す
分割
配列 A[p..r] を 2 つの(空の可能性もある)部分配列 A[p..q-1] と A[q+1..r] に、A[p..q-1] のどの要素も A[q] 以下となり、A[q+1..r] のどの要素も A[q] 以上となるように分割(再配置) する。添字 q はこの分割手続きの中で計算する
統治
2 つの部分配列 A[p..q-1] と A[q+1..r] をクイックソートを再帰的に呼び出すことでソートする
結合
2 つの部分配列はソート済みだから、これらを結合するために必要な仕事はない。配列全体 A[p..r] はソートされている
QUICKSORT(A, p, r)
if p < r
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q - 1)
  QUICKSORT(A, q + 1, r)
​
PARTITION(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
  if A[j] <= x
    i = i + 1
    A[i] を A[j] と交換する
A[i + 1] を A[r] と交換する
return i + 1
乱択版クイックソート
5.3 節では入力を明示的に置換することでアルゴリズムを乱択化した。しかし、無作為抽出(random sampling) と呼ばれる別の乱択化手法を用いると解析が簡単になる
これは A[r] を常にピボットとする代わりに部分配列 A[p..r] から要素を無作為に抽出し、それをピボットとして用いる
乱択版クイックソートは、PARTITION の代わりに RANDOMIZED-PARTITION を呼び出す
RANDOMIZED-PARTITION(A, p, r)
i = RANDOM(p, r)
A[r] と A[i] を交換する
return PARTITION(A, p, r)
​
RANDOMIZED-QUICKSORT(A, p, r)
if p < r
  q = RANDOMIZED-PARTITION(A, p, r)
  RANDOMIZED-QUICKSORT(A, p, q - 1)
  RANDOMIZED-QUICKSORT(A, q + 1, r)
クイックソートの性能
クイックソートの実行時間はピボットとなる要素に依存する
最悪の分割
分割手続きが元の問題を要素数 n - 1 の部分問題と要素数 0 の部分問題に分割した時
T(n) = θ(n^2) となる
最良の分割
各サイズが高々 n / 2 の部分問題となるよう分割した時
T(n) = θ(n * lg n) となる
クイックソートの平均実行時間は最悪の場合よりも最良の場合に近い
分割アルゴリズムが常に 9:1 で分割するとしても総コストは θ(n * lg n) である
クイックソートの解析
比較総数の期待値を計算すると Ｏ(n * lg n) となる。詳しくは p149
8: 線形時間ソート
決定木モデル(decision tree)
比較ソートは決定木の概念を用いて抽象的に表現できる
決定木は与えられたサイズの入力上で動作する特定のソーティングアルゴリズムが実行する要素間の比較を表現する全 2 分木である
すべての置換が、到達可能な葉として出現する
最悪時の下界
決定木の根から任意の葉までの単純パスの長さの最大値が、対応するソーティングアルゴリズムの最大比較回数となる
任意の比較ソートアルゴリズムは最悪時に Ω(n * lg n) 回の比較が必要(定理 8.1)
計数ソート(counting sort)
n 個の入力要素はある整数 k に対して 0 から k の範囲の整数から選ばれると仮定する
k = Ｏ(n) ならば計数ソートは Ｏ(n) 時間で走る
計数ソートは比較ソートではないので、下界 Ω(n * lg n) を超えることができる
COUNTING-SORT(A, B, k)
C[0..k] を新しい配列とする
for i = 0 to k
  C[i] = 0
for j = 1 to A.length
  C[A[j]] = C[A[j]] + 1 // C[i] は i と等しい要素の数を示す
for i = 1 to k
  C[i] = C[i] + C[i - 1] // C[i] は i 以下の要素の数を示す
for j = A.length downto 1
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]] - 1
安定性(stability)
同じ値の要素は入力に出現する順序で、出力に出現するという性質
計数ソートはこの安全性を保証する
基数ソート(radix sort)
紙パンチカードのためのソート機械が用いていたアルゴリズム
最下位の桁から順にソートしていく。ただし、各桁のソートは安定でなければならない
計数ソートを安定な中間ソートに用いる基数ソートはその場でのソートではないという欠点もある
主記憶領域が高価な時は、クイックソートのようなその場でのソーティングアルゴリズムを選択することもある
RADIX-SORT
for i = 1 to d
  安定ソートを用いて、第 i 桁に関して配列 A をソートする
バケツソート(bucket sort)
バケツソートは入力が一様分布から抽出されると仮定する時、平均実行時間 Ｏ(n) を達成する
バケツソートは入力を n 個の等しい大きさのバケツと呼ぶ部分区間に入力し、n 個の入力をバケツに分配する
BUCKET-SORT(A)
n = A.length
B[0..n-1] を新しい配列とする
for i = 0 to n - 1
  B[i] を空リストに初期化する
for i = 1 to n
  A[i] をリスト B[[nA(i)]] に挿入する
for i = 0 to n - 1
  リスト B[i] を挿入ソートでソートする
リスト B[0], B[1],...,B[n - 1] をこの順序で連結する
9: 中央値と順序統計量
順序統計量(ith order statistic)
n 個の要素を持つ集合の i 番目の順序統計量はその集合の中で i 番目に小さい要素である
最小値の決定
MINIMUM(A)
min = A[1]
for i = 2 to A.length
  if min > A[i]
    min = A[i]
return min
線形期待時間選択アルゴリズム
期待実行時間 θ(n) で i 番目に小さい要素を返すアルゴリズムを検討する。RANDOMIZED-SELECT は上記の条件を満たす
RANDOMIZED-SELECT
配列 A[p..r] の i 番目に小さい要素を返す
最悪実行時間は θ(n^2) だが、期待実行時間は Ｏ(n)
RANDOMIZED-SELECT(A, p, r, i)
if p == r
  return A[p]
q = RANDOMIZED-PARTITION(A, p, r)
k = q - p + 1
if i == k // ピボット値が答
  return A[q]
else if i < k
  return RANDOMIZED-SELECT(A, p, q - 1, i)
else
  return RANDOMIZED-SELECT(A, q + 1, r, i - k)
線形最悪時間選択アルゴリズム
最悪実行時間が Ｏ(n) の選択アルゴリズムを検討する。SELECT は上記の条件を満たす
SELECT
最悪実行時間 Ｏ(n) で配列を必ず上手に分割する
手順
1: 要素数 n の入力配列をそれぞれ 5 個の要素からなる n/5 個のグループと残りの n mod 5 個の要素からなる高々 1 個のグループに分割する
2: 各グループの(高々 5 個の)要素を挿入ソートによってソートし、ソートされた n/5 個のグループのそれぞれから中央値を選択する
3: SELECT を再帰的に用いて、ステップ 2 で発見した n/5 個の中央値の中央値 x を発見する
4: 修正版の PARTITION を用いて入力配列を入力配列を中央値の中央値 x をピボットとして分割する。k を分割の下側(x よりも小さい要素の集合)に属する要素数 +1 とする。この時、x は k 番目に小さい値であり、分割の上側には n - k 個の要素が属する
5: i = k ならば x を返す。i < k ならば、分割の下側から i 番目に小さい要素を SELECT を再帰的に用いて発見し、i > k ならば、分割の上側から (i - k) 番目に小さい要素を SELECT を再帰的に用いて発見する
実行時間
T(n) <= Ｏ(1) n < 140 の場合
T(n) <= T(n/5) + T(7n/10 + 6) + Ｏ(n) n >= 140 の場合
これを解くと、最悪実行時間が線形になることがわかる
Ⅲ: データ構造
数学の集合は変化しないが、アルゴリズムが扱う集合は成長したり、縮んだり、時間とともに変化する。この集合を動的であるという
10 章ではスタック、キュー、連結リスト、根付き木のような単純なデータ構造を扱う上でキーとなることを説明する
11 章ではハッシュ表、12 章では 2 分探索木を扱う
13 章で 2 分探索木の改良である 2 色木、14 章では 2 色木を補強する方法を示す
10: 基本データ構造
スタックとキュー
スタックとキューは削除操作 DELETE が決まった要素を削除する動的集合である
スタックは最後に挿入した要素を削除する。後入れ先出し(LIFO: last-in, first-out)方策を実現する
キューは集合に最も長時間滞在した要素を削除し、先入れ先出し(FIFO: first-in, first-out)方策を実現する
スタック(stack)
スタックでは INSERT 操作を PUSH、DELETE 操作を POP と呼ぶ
STACK-EMPTY(S)
if S.top == 0
  return TRUE
else
  return FALSE
​
PUSH(S)
S.top = S.top + 1
S[S.top] = x
​
POP(S)
if STACK-EMPTY(S)
  error "アンダーフロー"
else
  S.top = S.top - 1
  return S[S.top + 1]
キュー(queue)
キューでは挿入操作 INSERT を ENQUEUE、削除操作 DELETE を DEQUEUE と呼ぶ
操作の実行にはそれぞれ Ｏ(1) 時間かかる
ENQUEUE(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
  Q.tail = 1
else
  Q.tail = Q.tail + 1
​
DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
  Q.head = 1
else
  Q.head = Q.head + 1
return x
連結リスト(linked list)
オブジェクトがある順序で一列に並ぶデータ構造を連結リストという
配列では添字によってオブジェクトの線形順序が決まるが、連結リストの線形順序は各オブジェクトが持つポインタによって決まる
いくつかの種類がある。一方向 / 双方向、ソート済み / 未ソート、循環 / 非循環、がある
双方向連結リスト(doubly linked list)
双方向連結リスト L の各要素はキー属性 key と 2 つのポインタ属性、next と prev を持つオブジェクト
循環リスト(circular list)
リストの先頭の prev ポインタがリストの末尾を指し、末尾の next ポインタがリストの先頭を指す
以下では、未ソート双方向連結リストを仮定して議論を進める
連結リストの探索
手続き LIST-SEARCH(L, k) は、簡単な線形探索によってリスト L からキー k を持つ最初の要素を発見し、その要素を指すポインタを返す
LIST-SEARCH(L, k)
x = L.head
while x != NIL かつ x.key != k
  x = x.next
return x
連結リストへの挿入
x を連結リストの先頭に継ぎ足す
LIST-INSERT(L, x)
x.next = L.head
if L.head != NIL
  L.head.prev = x
L.head = x
x.prev = NIL
連結リストからの削除
LIST-DELETE(L, x)
if x.prev != NIL
  x.prev.next = x.next
else
  L.head = x.next
if x.next != NIL
  x.next.prev = x.prev
連結リストの先頭と末尾の境界条件が無視できるならば、LIST-DELETE のコードはもっと簡単になる
LIST-DELETE'(L, x)
x.prev.next = x.next
x.next.prev = x.prev
番兵(sentinel)
番兵は境界条件を簡略化するためのダミーオブジェクト
通常の双方向リストを番兵を持つ双方向循環リストに変える。リストの先頭と末尾の間に番兵 L.nil が置かれ、属性 L.nil.next がリストの先頭を、L.nil.prev がリストの末尾を指す
ポインタやオブジェクトが提供されていない言語で、連結データ構造を実現する 2 つの方法
オブジェクトの多重配列表現
オブジェクトの単一配列表現
オブジェクトの割付けと解放
あるキーを双方向連結リストが表現する動的集合に挿入するには、連結リスト表現の中から現在使用されていないオブジェクトを見つけ、それにポインタを割り付ける必要がある
この未使用オブジェクトを未使用リストと呼ぶ一方向リストとして管理する
未使用リスト(free list)
多重配列表現が使用する配列の長さを m とし、ある時点で動的集合が n <= m 個の要素を含むとする
n 個のオブジェクトが動的集合の要素を表現し、残りの m - n 個のオブジェクトは未使用(free)である
未使用リストは配列 next だけを使用し、そこに未使用リストの next ポインタを格納する
オブジェクトの割付けと解放は以下のように行う
ALLOCATE-OBJECT()
if free == NIL
  error = "容量不足"
else
  x = free
  free = x.next
  return x
​
FREE-OBJECT(x)
x.next = free
free = x
上で紹介したリスト表現方法は、任意の均質なデータ構造に拡張できる。ここでは、その中から根付き木ポインタに基づくデータ構造によって表現する問題を考察する
根付き木の表現
2 分木
属性 p、left、right を用いて 2 分木 T の各節点の親、左の子、右の子を指すポインタを格納する
分岐数に制約のない根付き木
左-子、右-兄弟表現(left-child, right-sibling representation)
2 つのポインタを持つ
x.left-child は節点 x の最左の子を指す
x.right-sibling は x のすぐ右の兄弟を指す
これら以外にも、根付き木は別の方法で表現できる
11: ハッシュ表
ハッシュ表と配列の直接アドレス指定法
出現可能なキーの個数に比べ、実際に格納されるキーの個数が少ない場合には、実際に格納されるキーの個数に比例する大きさの配列しか使用しないハッシュ表が、配列に対する直接アドレス指定法に代わる効果的な手法となる
直接アドレス表(direct-address table)
出現する可能性のあるキーの全集合 U がそれほど大きくない場合に、直接アドレス指定法はうまく働く
動的集合を表現するために、直接アドレス表と呼ぶ配列 T[0..m-1] を用いる
配列の各位置を枠(slot)と呼ぶ
辞書操作の実現は以下。どれも Ｏ(1) 時間で走る
DIRECT-ADDRESS-SEARCH(T, k)
return T[k]
​
DIRECT-ADDRESS-INSERT(T, x)
T[x.key] = x
​
DIRECT-ADDRESS-DELETE(T, x)
T[x.key] = NIL
ハッシュ表
直接アドレス表の弱点
キーの普遍集合 U が非常に大きい時は、利用可能な記憶領域上に表 T を格納できない
実際に格納されるキーの集合が U に比較して非常に小さい時には、T に割り付けられた領域のほとんどが無駄になる
直接アドレス指定法では、キー k を持つ要素は枠 k に格納する。ハッシュ法では、この要素を枠 h(k) に格納する
キー k から枠を計算するためにハッシュ関数(hash function) h を用いる
h はキーの普遍集合 U からハッシュ表(hash table) T[0..m-1] の枠の集合への写像、すなわち h: U → {0, 1, ..., m - 1} であり、普通ハッシュ表のサイズ m は |U| に比べて十分に小さい
衝突(collision)
同じ枠に 2 つのキーがハッシュされる可能性があること
チェイン法(chaining)
チェイン法では同じ枠にハッシュされた全ての要素を 1 つの連結リストに置く。枠 j に格納されるのは、j にハッシュされた全ての要素を格納するリストの先頭を指すポインタである
CHAINED-HASH-INSERT(T, x)
x をリスト T[h(x.key)] の先頭に挿入する
​
CHAINED-HASH-SEARCH(T, k)
リスト T[h(k)] の中からキー k を持つ要素を探索する
​
CHAINED-HASH-SEARCH(T, x)
リスト T[h(x.key)] から x を削除する
チェイン法を用いるハッシュ法の解析
負荷率(load factor)
n 個の要素を格納している枠数 m のハッシュ表 T の負荷率 α を n / m で定義する。すなわち、α は 1 つのチェインに格納されている要素数の平均
最悪時は n 個のキーが全て同じ枠に入り、探索時間は θ(n) とハッシュ関数の計算時間の和となる
単純一様ハッシュ(simple uniform hashing)仮定
任意に与えられた要素は、他の要素が既にどの枠にハッシュされたかとは無関係に、m 個の任意の枠に等確率でハッシュされると仮定する
失敗に終わる探索、成功に終わる探索どちらの時間の平均も θ(1 + α)
ハッシュ関数
優れたハッシュ関数の条件
単純一様ハッシュ仮定を満足すること
除算法
h(k) = k mod m
乗算法
最初、キー k にある定数 A(0 < A < 1) をかけ、kA の小数部分を取り出す。続いてこの値に m をかけ、結果の小数部分を切り捨てる
万能ハッシュ法
悪意を持った敵対者がハッシュされるキーを選択するならば、同じ枠にハッシュされる n 個のキーを選択する。この場合、ハッシュ表の最悪検索時間は θ(n) になる
この状況を打開するための有効な唯一の手段は、格納されつつあるキーとは独立にハッシュ関数をランダムに選択すること
万能ハッシュ法では、利用するハッシュ関数を実行開始時に、関数の集合の中からランダムに選択する
こうすると、敵対者が常に最悪になる操作系列を選択することは不可能となり、ハッシュ関数の選択をうまくランダム化することで、どんな操作の列も短い平均実行時間で処理できることが保証される
オープンアドレス指定法(open addressing)
表の各枠に格納されているのは動的集合の要素か NIL
チェイン法のように、表の外部にリストを持ち、そこに要素を格納することはしない。したがって、負荷率 α は 1 を超えない
ポインタを格納しないことで空いた記憶はハッシュ表の一部に還元され、同じ記憶料でより多くの枠が実現できる
挿入
挿入を実行するには、キーを置くことができる空の枠に出会うまでハッシュ表を次々と検査、あるいは探査(probe)する
枠を探査する順序は、その時挿入しようとしているキーに依存して決める
キーの削除
あるキーを枠 i から削除する時、そこに NIL を格納し、i が空であることを示すだけでは不十分
NIL の代わりに特別な値 DELETED を格納することで探索を続ける
HASH-INSERT(T, k)
i = 0
repeat
  j = h(k, i)
  if T[j] == NIL
    T[j] = k
    return j
  else
    i = i + 1
until i == m
error "ハッシュ表オーバーフロー"
​
HASH-SEARCH
i = 0
repeat
  j = h(k, i)
  if T[j] == k
    return j
  i = i + 1
until T[j] == NIL または i == m
return NIL
オープンアドレス指定法で頻繁に用いられる 3 つの手法
線形探査法(linear probing)
i = 0, 1, ..., m - 1 に対して、ハッシュ関数 h(k, i) = (h'(k) + i) mod m を用いる
h' を補助ハッシュ関数(auxiliary hash function)と呼ぶ
キー k が与えられた時、最初に T[h'(k)] を探索し、次に T[h'(k) + 1] と順々に探査していく。T[m - 1] までいったら T[0], T[1] の順で T[h'(k) - 1] まで探査する
主クラスタ化(primary clustering)の問題
長い区間の枠がすべて使用中になり、平均探査時間が悪化する問題
連続する i 個の使用中の枠に続く空の枠が次に使用される確率が (i + 1) / m であることがクラスタが現れる理由