MIT OCW 6.006 Lecture 1: Peak-finder ノート
Lecture 1で紹介された問題「Peak-finder」に関するノートと考えたことのまとめ。
One-dimensinal version
Problem
Find a peak if it exists.
1 2 3 4 5 6 7 8 9
a b c d e f g h i
a~i: integer
表記: {1}=a, {2}=b, ... , {9}=i
- Position 2 is a peak if and only if b >= a and b >= c.
- Position 9 is a peak if and only if i >= h.
Argue：Peakは常に存在するか？
Yes.
- 要素数が１の場合はその要素がPeak
- 要素数が２以上で、Peakではない要素のみからなる配列が存在すると仮定し、その構築を試みる。
- {1}はPeakではない。よって{1} < {2}
- {2}も同様。よって{1} < {2} < {3}
- ...
- {1} < {2} < ... < {N} (Nは配列の要素数)
- このとき{N}はPeakになり、仮定に反する。
Solution：Straightforward Algorithm
左から順に要素がPeakであるか確認する。
計算量：O(N)
- 最悪のケースは単調増加数列。すべての要素を調べることになる。
- 平均的には N/2 個の要素を調べることになる。
左から順ではなく中央の要素から確認するようにした場合、計算量は依然O(N)だが、調べる要素の個数は最悪でもN/2個、平均でN/4個になる。
Solution: Divide & Conquer
以下の要領で探索範囲の大きさを半分に限定していく。
- {n/2} < {n/2-1} の場合、 {1} ~ {n/2-1} にPeakがある。
- {n/2} < {n/2+1} の場合、 {n/2+1} ~ {n} にPeakがある。
- いずれでもない場合は、{n/2}がPeak
計算量：O(lgN)
- T(N)を計算量とする。
- T(N)
- = T(n/2) + O(1)
- = T(n/4) + O(1) + O(1)
- = ...
- = O(1) + ... + O(1) (lgN times)
- = O(lgN)
Argue: Is That Algorithm Correct?
- 探索範囲 {s} ~ {e} が、常に {s} < {s+1} と {e} < {e-1} を満たす場合：
- 探索範囲に含まれる要素の数が1 or 2のとき、この条件は満たせない。
- 探索範囲に含まれる要素の数が3のとき、この条件を満たすのは {s} < {s+1} > {s+2 = e} のケースのみなので次のステップで見つかる
- 探索範囲に含まれる要素の数が3より大きくても、探索範囲を狭めていくといずれ要素数が3になって見つかる
{1} >= {2} or {N} >= {N-1} の場合上記の前提が満たされないが、この場合は最悪のケースでも探索範囲が{1} ~ {N} => {1} ~ {N/2} => ... {1} ~ {2} などとなるのでlgNステップで見つかる。
Two-dimensional version
Problem
Find a 2D-peak if it exists.
_ c _ _
b a d _
_ e _ _
_ _ _ _
N rows, M columns
a~d, _: integer
表記: {1,2}=c, {2,1}=b, {2,2}=a, {2,3}=d, {3,2}=e
- a is a 2D-peak if a>=b, a>=c, a>=d, a>=e.
Attempt: Extend 1D Divide and Conquer to 2D
j=M/2 _ * _ _ i * * * * _ * _ _ _ * _ _
- 中央の列j=m/2をとり、1D-peakを見つける。（行iに見つけたとする）
- 行iの中で1D-peakを見つける。これを2D-peakとする。
問題点：2D-peakが行iにあるとは限らない
うまくいかない例： __ __ 10 __ 14 13 12 __ 15 9 11 __ 16 17 19 20
Attempt:
- 中央の列j=m/2をとる。
- 列j内の最大値を見つける。（見つけた場所を(i,j)とする）
- (i,j) < (i,j-1)なら左側を残す。
- (i,j) < (i,j+1)なら右側を残す。
- どちらでもないなら(i,j)は2D-peak。
- 残り１列になったら、列内の最大値が2D-peak。
計算量：O(NlgM)
- T(N,M)を計算量とする。
- T(N,M)
- = T(N,M/2) + O(N)
- = T(N,M/4) + O(N) + O(N)
- = ...
- = O(N) + ... + O(N) (lgM times)
- = O(NlgM)
Is That Algorithm Right?
たとえばこういうケース
2 7 3 8 4 7 5 6
列1の最大値は{4,1}=5。{4,1}<{4,2}なので探索範囲を列2に絞るが、この時点で{列1の任意の値} <= {列2の最大値}が確定する。
このように、探索範囲内に残った両端の列の最大値は、隣接する探索範囲外の列の値に対して常に2D-peakの条件を満たす。したがって、最後の１列になるまで探索範囲を限定し、列内で最大値をとればそれは2D-peak。
ちなみに、列内の最大値をとる代わりに列内の1D-peakを使用した場合は上記の性質が失われるので、たとえば以下のケースで2D-peak検出に失敗する。
2 3
3 4
2 5
9 6
2D-peakは{1,4}=9のみだが、{2,4}=6が検出される！
