9章縮小法杉原厚吉．（２００１）.「データ構造とアルゴリズム」. 東京：共立出版. 情報知能学科「アルゴリズムとデータ構造」担当：白井英俊 9章の目的 • 5章で分割統治法を学んだ • 分割統治法は、問題を小問題に分解して解くアルゴリズム設計原理 • 小問題の大きさの合計が元の問題の大きさより小さい場合の分解法を「縮小法」という • 縮小法は、特に効率的なアルゴリズムとなる 9.1 問題の規模縮小化 • 分割統治法：大きさ大きさnの問題を、a個の小問題に分割し、それぞれの小問題の大きさがn/bになる場合を考えた小問題(n/b) 問題全体 … (サイズn) a個小問題(n/b) 小問題(n/b) 縮小法: n ＞a*(n/b) となるように問題を分解延べサイズ＝a * (n/b) 問題の規模縮小化 • より一般に… 大きさnの問題Pが、Pと同じ形式の小問題P1, P2, …, Pk に分解でき、それぞれの小問題の大きさが s1*n,s2*n,…, sk*nであり 0 < s1, s2, …, sk < 1、かつ s1+s2+…+sk< 1 (9.1) 問題の大きさがn0 以下の場合は分解しないとする。計算時間をf(n)とおくと (9.2) f(n) = c (n ≦ n0 ) f(s1*n)+ f(s1*n)+… f(s1*n)+c*n (n > n0 ) を満たすとき、 f(n) = O(n) 9.2 定順位要素の抽出問題：n個の実数の集合S={x1, x2, …, xn}と整数 kが与えられた時、Sの中で小さい方から順位がk番目の要素を抽出する素直な解き方： Sをソートしてk番目の要素を取り出す計算量はO(n logn) よりよい方法：縮小法を用いる。ソートしないので、計算量はO(n) 縮小法による定順位要素の抽出アルゴリズム Order(S, k) |S|<100 のとき、Sの要素をソートし、k番目の要素を取り出して処理を終了 5個ずつのグループの3番目の要素だから、そのグループの中央値 2. |S| ≧100 のとき（n= |S| とする) ① Sの要素を5個ずつのグループにわけ、各グループの中から順位3番目のものを取り出し、それらを集めた集合をTとする ② m ← Order(T, n / 10 ) Tの個数はn/5ある ③ Sをmより小さいものの集合S1 、 mと等しいものの集合S2 、mより大きいものの集合S3 へ分割 mは中央値の中央値 ④ k ≦ |S1| なら y←Order(S1, k) |S1| < k ≦ |S1| +|S2|なら y ←m |S1| +|S2| < k なら y←Order(S3, k －|S1| － |S2|) ⑤ yを出力して処理を終了 1. 実習 • 縮小法による定順位要素の抽出は、かなり要素数が大きい集合に対するもの。 • ここでは「感触」をつかんでもらうため、アルゴリズムにおける「１００を１０で置き換え」て、以下のデータに対し試してみよう。(n=30, k=10) 056, 927, 234, 048, 804, 055, 565, 585, 333, 250, 457, 369, 552, 488, 642, 274, 500, 783, 812, 984, 087, 528, 749, 092, 043, 618, 194, 796, 123, 196 実習（続き） 5個ずつのグループ 30/10=3番目の要素 S= { { 056, 048, 927, 056, 234, 234, 048, 804, 804 927 }, { 055, 055, 250, 565, 333, 585, 565, 333, 585 250 }, { 369, 457, 457, 369, 488, 552, 552, 488, 642 642 }, { 274, 500, 783, 812, 984 }, { 043, 087, 087, 528, 092, 749, 528, 092, 749 043 }, { 123, 618, 194, 196, 796, 618, 123, 796 196 } } 3番目の要素これに続けて試してみよう！計算量の問題 • 定順位要素の抽出は次のようにしてもO(n)で実行できる（？）。この方法と縮小法との計算量を比較せよ。 • 手続き：入力：n個の数の集合S、出力：小さい方からk番目最大要素だけが重要なのでヒープを使うと効率的の要素 1. 最初のk個をソートしておく。それをTとする。 2. (n-k)個の要素それぞれ(xとする)に対し、Tの最大要素(yとする)と比較。小さい時に限り、T-{y}+{x} (Tからyを取り除きxを足した集合)をソートする。 3. Tの最大要素が答え。