人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

【アルゴリズムを教えてください】
要素数 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] を求めたい。

●質問者: akagi_paon
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:いもの アルゴリズム 素数 配列
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● 犬猫ハーフ
●100ポイント ベストアンサー

アルゴリズムとして名前があるかは不明ですが、今思い付いたアルゴリズムを書きます。

(質問文の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)になります。

◎質問者からの返答

えーと、O(nm^2) は O(n×m×m) の意味です。

単純に全体をなめるアルゴリズムでも O(n×m×m) でできますよね?

とりあえず実装してみて使えそうならポイント差し上げます。

----

実装してみました。

ハッキリ言って、むちゃくちゃ速くなりました!

今まで20分ほどかかっていた処理が50秒で終わりました\(^o^)/

ありがとうございました!

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ