【アルゴリズムを教えてください】
要素数 m の配列が n 個あるとします。
一つめの配列のそれぞれの要素が全体で小さいほうから何番目に
あるかを算出するアルゴリズムで、O(nm^2) より小さいものを教えてください。
ただし、同順位の場合は順位の平均を求めるものとします。
例：(m = 4, n = 3)
[21, 11, 16, 19]
[20, 15, 12, 17]
[14, 21, 18, 13]
が与えられたとき、[11.5, 1, 6, 9] を求めたい。
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。
ログインして回答する
ベストアンサー
-
犬猫ハーフ
満足100pt
アルゴリズムとして名前があるかは不明ですが、今思い付いたアルゴリズムを書きます。
（質問文のO(nm^2)はO((nm)^2)だと考えて、要求を満たすものだと考えました。私の思い違いでしたら申し訳ありません。）
1. 全ての配列を1つの（mn要素の）配列にまとめる（O(mn)）
2. 上記の配列をソートする（適切なアルゴリズムを使えばO(mn log(mn))）
3. ソート済みの配列から必要な順位を計算する（大体O((m^2)n)?）
質問文の例だと
1. [21, 11, 16, 19, 20, 15, 12, 17, 14, 21, 18, 13]
2. [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21]
3. ソート済みの配列から、21の平均順位は11.5、11の順位は1、…
3.の処理ですが、ソート済みの配列から任意の一要素（例えば11）を見つけるのは二分探索でO(m log(mn))。そこから同順位の要素を探すのが（1個あたりのワーストケースが）O(mn)なので、3.のオーダーはO((m^2)n)ではないかと。
という訳で、全体のオーダーは3.のO((m^2)n)になります。
-
akagi_paon
-
akagi_paonその他の回答
この質問へのコメント
質問の情報
- 登録日時
- 2009-05-08 14:48:04
- 終了日時
- 2009-05-08 18:28:45
- 回答条件
- 1人2回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
この英文どうなってますか？ The boy seemed to be waiting for his mother to come.（その少年は母親が来…
匿名質問者
1
1
-
不定詞の形容詞的用法らしいんですけど、副詞的用法と書いたら✖️ですか？ I want to buy a book to read …匿名質問者11
-
日向陽葵という○V女優が好きなのですが似ている○V女優はいますか匿名質問者
-
共通テストで使われるプログラミング言語は共通テスト特有の言語と聞いたのですが、受験勉強で身につけたプ…匿名質問者1
-
内定してほしいポケモンはいますか？匿名質問者
そうでしたか、失礼しました。
そこで、考えた方法は、
まず例では、２１を全体から走査して順位を出します。
そのときに、各要素を２１より大きい物と小さい物の２つの要素分けます。
次に、１１の順位を出すときに２１より小さいので先ほどの小さい物を集めた要素から順位を出します。
このように、一つ前の要素を利用して短縮することで、O(nm^2)より早くなります。
対象となる先頭の配列のみソートしていますが、あとは１回のスキャンで
終わっているので、計算量としては O(mn)になります。
n が十分大きい場合には有効かと思います。
<html>
<head>
<script type="text/javascript">
<!--
function arrayRanking(){
var ar1=document.getElementsByName("ar1");
var ars=document.getElementsByName("ar");
var ans=document.getElementsByName("ans");
var backet = Array( ar1.length * 2 );
var base = Array( ar1.length );
for ( var i=0 ; i< ar1.length ; i++ ) {
if ( isNaN( ar1[i].value ) ) {
alert("未入力データがあります。" );
return;
}
base[i] = ar1[i].value;
}
base.sort( cmp );
// データの初期化
for ( var i=0 ; i< ar1.length ; i++ ) {
backet[2*i] = 0;
backet[2*i + 1] = 1;
}
// データのチェック
for ( var i=0 ; i< ars.length ; i++ ) {
if ( isNaN( ars[i].value ) ) {
alert("未入力データがあります。" );
return;
}
}
// 集計処理
for ( var i=0 ; i< ars.length ; i++ ) {
for( var j=0 ; j<base.length ; j++ ) {
if ( ars[i].value < base[j] ) {
( backet[2 * j] )++;
break;
}
if ( ars[i].value == base[j] ) {
backet[2 * j + 1]++;
break;
}
}
}
// 結果の集計
var sum = 0;
for ( var i=0 ; i<base.length ; i++ ) {
sum += backet[2*i];
for( var j=0 ; j<ar1.length ; j++ ) {
if ( Number( ar1[j].value ) == base[i] ) {
ans[j].value = sum + 1 + (backet[2*i+1] == 1 ? 0 : 1 ) / backet[2*i+1];
}
}
sum += backet[2*i + 1];
}
}
function cmp( a, b ){
return ( a > b ) ? 1 : -1;
}
-->
</script>
</head>
<body>
<input type="text" name="ar1" value="21">
<input type="text" name="ar1" value="11">
<input type="text" name="ar1" value="16">
<input type="text" name="ar1" value="19">
<br>
<input type="text" name="ar" value="20">
<input type="text" name="ar" value="15">
<input type="text" name="ar" value="12">
<input type="text" name="ar" value="17">
<br>
<input type="text" name="ar" value="14">
<input type="text" name="ar" value="21">
<input type="text" name="ar" value="18">
<input type="text" name="ar" value="13">
<br>
<br>
<br>
<input type="button" value="実行" onclick="arrayRanking();">
<br>
<br>
<input type="text" name="ans">
<input type="text" name="ans">
<input type="text" name="ans">
<input type="text" name="ans">
<br>
</body>
</html>
特に Mook さんのは休みが明けたら実装してみようかと思います
(JavaScriptはあんまりわかんないんですよね・・・)
一番上の段を[1,2,3,4]にすると結果が[1,8,11,12]になるんですけど・・・
なにか間違ってませんか？
// 集計処理
for ( var i=0 ; i< ars.length ; i++ ) {
for( var j=0 ; j<base.length ; j++ ) {
if ( Number(ars[i].value) < base[j] ) {
( backet[2 * j] )++;
break;
}
if ( Number(ars[i].value) == base[j] ) {
backet[2 * j + 1]++;
break;
}
}
}
のように
ars[i].value
を
Number(ars[i].value)
に変えてください。
SALINGERさんのアイデアは面白いですね。一度処理した結果を流用するというのは私には思い付きませんでした。
とりあえずアルゴリズムの説明です。
（１）計測対象の配列（1列目：サイズ N）だけをソートした配列を用意します。
（このとき元の順番を示す情報を作成しておくと結果の処理が楽になりそうです）。
DataArray[N] （JavaScript では base[N] ）
（２）計測用の配列（サイズ N）を二つ用意します（例示では面倒なので ２Nの配列にしました）。
LessThanArray[N] （JavaScript では backet[2N] ・・・・正しい綴りは bucket でした。）
SameArray[N]
（３）すべてのデータを先頭配列のN番目のデータより小さい、N番目のデータに等しい、に応じてカウントします。
LessThanArray[i] は DataArray[i-1] より大きく DataArray[i] より小さいものの数
SameArray[i] は DataArray[i] と等しいものの数
（４）DataArray[i] の順位は 次の式になります。
DataArray[i] の順位 =（ LessThanArray[0] から LessThanArray[i] までの和 ）＋ １ ＋（※ 同じものがある場合の勘案分）
※の処理があいまいな部分があるのですが、11番目のものが４つあったら 11.25 になるのですか？
であれば、JavaScript にあるように、SameArray[i] が2以上の場合のみ、
（４）に （ 1 / SameArray[i] ）を足します。
各データを処理する部分は（３）のデータを計数する部分のみですので、O(mn)になるかと思います。
どうでもよい話ですが、
O(...)というのは係数を無視した計算量のオーダーを示す表現なので
実際の計算量が 100 × m × n でも 1/100 × m × n でも O(mn) となります。
例えばバブルソートの平均計算量は 1/2 n × n ですが、O(n^2) というように表現します。
だいたいつかめました。
ところで（３）の処理って O(nm^2) かかるような気がするんですけどどうでしょう？
テーブル全体をなめるのに O(mn)、LessThanArray の添字を出すのに(上のプログラムでは) O(m) かかっている気がします。
添字を求めるのにバイナリサーチを使えば O(nm*log(m)) くらいにはできそうですけど。
考え違いをしていたようです。
ただ、負け惜しみですが、m×n の要素全体をソートするコストは
クイックソートでもO(nm・log(mn))ですから、それよりは高速だと
思います。
mが大きいのであれば、バイナリサーチを使用したほうが良いかも
しれませんが、実例のように４程度であれば、単純な比較でも性能に
影響はなさそうな気もします。
実際の、ｍ、ｎはどのくらいの数値なのでしょうか。
m=300～100000, n=30～100 くらいです。
実装してみましたが、速度に関しては cdaotg さんのアルゴリズムも Mook さんのアルゴリズムもたいした違いは出ませんでした（Mook さんの方がちょっとだけ遅かった）
しかし、cdaotg さんのアルゴリズムでは配列を最初にすべて取り込んでおかないといけないのに対し、Mook さんのアルゴリズムでは逐次的に取り込めばいいので、消費メモリ量に格段に差が出ました。
よって、Mook さんのアルゴリズムを使おうと思います。
Mook さんありがとうございました。あとでポイント送信させていただきます。
あらら、期待していた状態とは逆に m の方がずっと大きいのですか。
であれば、cdaotg さんのアルゴリズムとさほど性能差はないですね。
実際にどの言語で実装されているのか、入出力のデータ形式がなんであるのか、
またデータ運用がどうであるかも興味のあるところですが、単純にアルゴリズムを
考えるだけでも興味深い問題で、こちらも楽しませていただきました。