小配列への分割方法

ウィキペディア小見出し辞書

小配列への分割方法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 15:10 UTC 版)

「中央値の中央値」の記事における「小配列への分割方法」の解説

先述の通り、本項で説明した中央値の中央値アルゴリズムでは、配列全体を5要素ずつの小配列に分割した。5要素ずつに分割した理由については以下のように説明できる。 奇数個の要素から成る小配列に分割するのが高速かつ簡便なため。偶数個の要素から成る小配列に分割することもできるが、その場合、真ん中の要素は2つになってしまい、中央値はその平均をとらなければならないので、唯一の中央値を簡単に選択できる奇数個に比べて遅くなる。 中央値の中央値アルゴリズムが動くのは1つの小配列には5要素以上が必要なため。もし3要素ずつしかない場合、小配列の中央値を抽出した配列の要素数は 1 3 n 個になる。また、各小配列の中に存在するピボット値以下・以上の値はそれぞれ2つずつとなるので、次の探索対象の配列は要素数が最悪でも 1 3 n × 1 2 × 2 = 1 3 n 個減少するので、残るのは ( 1 − 1 3 n ) = 2 3 n 個となる。ゆえに、結局、前者と後者を合わせて n 個の要素に対して選択アルゴリズムを必要としてしまうので、要素数が全く減らないことになる。 「5」は、中央値の中央値アルゴリズムが動くもののなかで最小値であるため。もし7個ずつ以上、 2 m + 1 ( m = 3 , 4 , 5... ) 個ずつの小配列に分割した場合、まず、小配列の中央値を抽出した配列の要素数は 1 2 m + 1 n 個になる。また、各小配列の中に存在するピボット値以下・以上の値はそれぞれ m + 1 個ずつとなるので、次の探索対象の配列は要素数が 1 2 m + 1 n × 1 2 × ( m + 1 ) = m + 1 4 m + 2 n 個減少するので、残るのは ( 1 − m + 1 4 m + 2 ) n = 3 m + 1 4 m + 2 n 個になる。ゆえに、結局、前者と後者を合わせて 3 m + 3 4 m + 2 n 個の要素に対して選択アルゴリズムを必要とする。つまり、ここでmを大きくして小配列の要素数を増やしたとしても、結局、次の探索対象の要素数は 3 4 n 個、つまり元の要素数の75%にしかならない。一方で小配列の中の要素数が増えていくと、分割処理にも小配列の中での中央値を探すのにも時間がかかるようになってしまい、元の配列の要素数が充分に大きくなると全体的な性能向上には寄与しなくなってしまう。 別の分割方法として、要素数が一定の小配列ではなく一定数の小配列に分割する、つまり、要素数が5個ずつの小配列ではなく、5個の小配列に分割することを考える。しかしその場合は、明らかに要素数は減少させることはできない。なぜなら、要素数 1 5 n 個ずつの小配列5個の中で、それぞれ中央値を計算せねばならないが、結局、次の探索対象の要素数は 7 10 n 個にしかならないからである。つまり、3要素ずつに分割する時と同様に、個々の中央値を計算する配列の要素数は元の配列より少なくて済むが、結局、全体的な長さは短くならず、むしろ長くなってしまう。要素数が n 個の小配列に分割しても、小配列の数は n 個になり、同様である。