]> アルゴリズムイントロダクション 第 9 章 中央値と順序統計量 (その 2)

中央値と順序統計量 (その 2)

nanto_vi (TOYAMA Nao)

最悪線形時間選択アルゴリズム

Select ⁡ A i 0 n ← A の要素数 1 A を 5 つずつのグループに分割 2 各グループの要素を任意の方法でソートし、 グループ内での中央値を求める 3 各グループの中央値の中央値 x を求める x ← Select ⁡ 各グループの中央値 1 2 ⁢ n 5 4 x をピボットとして A を A smaller と A larger に分割 A smaller ← x より小さい A の要素 A larger ← x より大きい A の要素 k ← A smaller の要素数 + 1 5 if i = k then return x elseif i < k then return Select ⁡ A smaller i else return Select ⁡ A larger i - k

実行時間の評価

x より大きい要素、小さい要素はそれぞれ少なくとも 3 ⁢ 1 2 ⁢ n 5 - 2 ≥ 3 ⁢ n 10 - 6 個存在するから、 A smaller , A larger の要素数はいずれも高々 n - 3 ⁢ n 10 - 6 = 7 ⁢ n 10 + 6 個。

[x より大きい要素の個数を表した図]

Select の実行時間を T ⁡ n とすると、各ステップの実行時間は、 1 O ⁡ n 2 O ⁡ 5 ⁢ lg ⁡ 5 · n 5 = O ⁡ n 3 T ⁡ n 5 4 O ⁡ n 5 T ⁡ 7 ⁢ n 10 + 6

ここで、ある定数 d に対して n < d で T ⁡ n = O ⁡ 1 と仮定すると、 T n ≤ { O ⁡ 1 n < d のとき T ⁡ n 5 + T ⁡ 7 ⁢ n 10 + 6 + O ⁡ n n ≥ d のとき

O ⁡ n はある定数 a を用いて a ⁢ n で抑えられる。ここで、ある定数 c に対して T ⁡ n ≤ c ⁢ n と仮定すると、 T ⁡ n ≤ c ⁢ n 5 + c ⁢ 7 ⁢ n 10 + 6 + a ⁢ n ≤ c ⁢ n 5 + 1 + c ⁢ 7 ⁢ n 10 + 6 + a ⁢ n = 9 ⁢ c ⁢ n 10 + 7 ⁢ c + a ⁢ n = c ⁢ n - c ⁢ n 10 - 7 ⁢ c - a ⁢ n = c ⁢ n - c - 10 ⁢ a 10 ⁢ n - 7 ⁢ c

ここで、 c > 10 ⁢ a とすると、 n ≥ 10 c - 10 ⁢ a ⁢ 7 ⁢ c = 70 + 700 ⁢ a c - 10 ⁢ a で T ⁡ n ≤ c ⁢ n だから、 T ⁡ n = O ⁡ n

3 つずつのグループに分割した場合

x より大きい要素、小さい要素はそれぞれ少なくとも 2 ⁢ 1 2 ⁢ n 3 - 2 ≥ n 3 - 4 個存在するから、 A smaller , A larger の要素数はいずれも高々 2 ⁢ n 3 + 4 個。よって、 T n ≤ T ⁡ n 3 + T ⁡ 2 ⁢ n 3 + 4 + O ⁡ n

O ⁡ n はある定数 a を用いて a ⁢ n で抑えられる。ここで、ある定数 c に対して T ⁡ n ≤ c ⁢ n と仮定すると、 T ⁡ n ≤ c ⁢ n 3 + c ⁢ 2 ⁢ n 3 + 4 + a ⁢ n ≤ c ⁢ n 3 + 1 + c ⁢ 2 ⁢ n 3 + 4 + a ⁢ n = c ⁢ n + 5 ⁢ c + a ⁢ n > c ⁢ n

よって、 T ⁡ n を c ⁢ n で抑えきれない。

7 つずつのグループに分割した場合

x より大きい要素、小さい要素はそれぞれ少なくとも 4 ⁢ 1 2 ⁢ n 7 - 2 ≥ 2 ⁢ n 7 - 8 個存在するから、 A smaller , A larger の要素数はいずれも高々 5 ⁢ n 7 + 8 個。よって、 T n ≤ T ⁡ n 7 + T ⁡ 5 ⁢ n 7 + 8 + O ⁡ n

O ⁡ n はある定数 a を用いて a ⁢ n で抑えられる。ここで、ある定数 c に対して T ⁡ n ≤ c ⁢ n と仮定すると、 T ⁡ n ≤ c ⁢ n 7 + c ⁢ 5 ⁢ n 7 + 8 + a ⁢ n ≤ c ⁢ n 7 + 1 + c ⁢ 5 ⁢ n 7 + 8 + a ⁢ n = 6 ⁢ c ⁢ n 7 + 9 ⁢ c + a ⁢ n = c ⁢ n - c ⁢ n 7 - 9 ⁢ c - a ⁢ n = c ⁢ n - c - 7 ⁢ a 7 ⁢ n - 9 ⁢ c

ここで、 c > 7 ⁢ a とすると、 n ≥ 7 c - 7 ⁢ a ⁢ 9 ⁢ c = 63 + 441 ⁢ a c - 7 ⁢ a で T ⁡ n ≤ c ⁢ n だから、 T ⁡ n = O ⁡ n

ただし、ステップ 2 の実行時間が、5 つずつのグループに分割した場合は O ⁡ 5 ⁢ lg ⁡ 5 · n 5 なのに対し、7 つずつのグループに分割した場合は O ⁡ 7 ⁢ lg ⁡ 7 · n 7 なので、定数 a の値はこちらのほうが大きい。

参考文献

  1. T. H. Cormen, C. H. Leiserson, R. L. Rivest, C. Stein, 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一, アルゴリズムイントロダクション 改定 2 版 第 1 巻 数学的基礎とデータ構造, 近代科学社
  2. 岩間一雄, アルゴリズム理論入門, 昭晃堂
  3. 茨木俊秀, C によるアルゴリズムとデータ構造, 昭晃堂