2011年12月9日金曜日

中央値を求めるアルゴリズム

基本というか、簡単に考えられるのは、

 - ソートしたのち、真ん中の要素を選択する

という方法だが、全ての要素をソートしないと答えが得られないというのは少し計算量が大きすぎる。

いろいろ調べてみると、クイックソートのアルゴリズムの発展型で、クイックセレクトなるアルゴリズムがあるらしい。

http://d.hatena.ne.jp/agw/20090505/1241602074
http://d.hatena.ne.jp/agw/20090513/1242290109

要するに、中央値が求まるくらいまでクイックソートを計算し、省略できる計算はしないということのようである。

このときに、クイックソートを計算するにあたり、最初に選択するパーティションの値をできるだけ中央値に近い値を選択するのが、アルゴリズムを高速化するコツであるということが書いてある。

http://d.hatena.ne.jp/hrk623/20110904/1315147736


また、メディアンフィルタのためのアルゴリズムで、3x3=9要素の中央値を求める高速なアルゴリズムについての文献があった。
http://www.ipsj.or.jp/10jigyo/fit/fit2002/LI_9.pdf

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。