アルゴリズム:効率の良い探索方法

アルゴリズムに関する質問です。
以下の問題をO(n)の時間で解くには、どのような方法を使えばいいのでしょうか？
どうぞよろしくお願い致します。

【問題】
とある店でm人いる顧客のうち、n人から契約更新の届けが来ました。
店側から届けが来ていない顧客(m － n人)へ契約更新のお知らせを出したいのですが、店にはソートされていない顧客の名前リストと、こちらもソートされていない契約更新をしたn人の名前リストしかありません。
m＝nだった場合は”なし”と、m＞nだった場合は契約更新をしていない顧客の名前を一人分アウトプットとして返しなさい。

No.6 ベストアンサー 回答者： nag0720 回答日時： 2014/11/07 14:25

#2, #4です。

失礼しました。とんでもない勘違いをしてました。#4は間違いです。無視してください。


で、m人の顧客の検索がO(n)であるという理由ですが、

m＞nだとして、m人のうちn人だけを検索します。
そのなかに１人でもハッシュテーブルにない顧客がいれば、それをアウトプットすればいい。
もしn人全員がハッシュテーブルに存在したとすれば、残りの顧客(m-n人)はすべて契約更新していないのだから、その中から適当に１人を選んでアウトプットすればいい。

いずれにしても、m人全員を検索する必要はなく、多くともn人の検索で充分なのでオーダーはO(n)になります。

この回答へのお礼

お礼を申し上げるのが大変遅くなってしまい、申し訳ございません。

nag0720様のおかげでどうしてハッシュテーブルを使えばO(n)時間で探索が完了出来るのか分かるようになりました。
丁寧に回答して下さって、感謝してもしきれません。
本当にありがとうございました！

お礼日時：2014/11/22 08:04

No.7 回答者： Tacosan 回答日時： 2014/11/10 23:52

残念ながら外れ.

大きな間違いは, 再帰の部分で計算量を nlogn としちゃってるところ. 確かに最悪 O(log n) 回の再帰が必要だから全体で O(n log n) となりそうなんだけど, 再帰をするごとにリストが短くなることを考慮して計算し直せばきっちり線形時間で終らせることができる. 解析は選択アルゴリズムと本質的に同じなので, 疑問に思ったら確認してみるといい (ただし Wikipedia の説明はちょっと日本語がこなれてないので読みにくいかも).

あとは細かいところで
・リスト全体の中央値を使うかわりにリストのまんなかにある値を使うと最悪の場合に計算量が大きくなるのでダメ (ここも本質は選択アルゴリズムと同じ: ここで線形時間使っても, アルゴリズム全体の時間は線形時間のまま)
・リストを m にすることに意味はない (リストの長さを 2n+1 にすることができる, というのは #6 の説明の通り)
というところかな.

あ, もちろん「想定する答え」は「ハッシュ」だと思うよ. というか, ハッシュ以外のアルゴリズムを想定するかなぁ, ふつう....

この回答へのお礼

お礼を申し上げるのが大変遅くなってしまい、申し訳ございません。

ゆっくり時間をかけて考え、計算したところ、Tacosan様がおっしゃっていたように線形時間で終わるアルゴリズムを作る事が出来ました。
細かい部分まで丁寧に説明して下さってどうもありがとうございました。
とても説明が分かりやすく、アルゴリズムが苦手な私にとっては大変ありがたかったです！

お礼日時：2014/11/22 08:02

No.5 回答者： Tacosan 回答日時： 2014/11/07 00:19

確認だけど, 「n個のデータの中央値が O(n) 時間で求まる」のはいいよね? それを前提に, 基本的な形 (ただしこの問題の答えではない) を書くとこんな感じ:

0. m = n だったら考えるまでもないので m > n の場合だけ考える.
1. 以下, もともとの「m人の顧客リスト」を「リスト1」, 「契約更新をした n人のリスト」を「リスト2」と呼ぶことにする.
2. 2つのリストをまぜて長さ m+n のリストを作る (どちらから来たデータであるかはわかるようにしておく).
3. このリストの中央値を見つける.
4-1. 中央値のデータがリスト1 から来た場合:
4-2. 同じ名前を持つリスト2 のデータを探す. あればそれらのデータを削除する, なければ「契約更新をしていない顧客の名前」が見付かったことになるので終了.
4-2': 同じ名前を持つリスト1 のデータとともに削除する.
5. (削除してしまった) 中央値でリストを二分する. 前半と後半のうち, どちらかは「リスト1 から来たデータの方が多い」ので, そちらに対して 3 以降を再帰的に実行する.

とここまで書いて次に宿題を出しておこう:
・このアルゴリズムの計算量は O(n) ではありません. 実際にはいくつでしょうか?
・計算量を O(n) にするにはいくつかの部分を修正する必要があります. どうすればよいでしょうか?

ちなみに計算量に関する #4 の記述は大嘘なので, 見なかったことにするか直ちに記憶から消去することをお勧めします.

この回答への補足

ご回答ありがとうございます！

以下、私が考えた宿題の回答(途中まで)です。
このアルゴリズムでしたら、中央値を見つけるのにO(m＋n)時間、4-2がワーストケースでO(n)時間、5は二分探索のようなものなのでO(log(m＋n))時間、計O(m＋n＋nlogn)時間かかると考えました。
それをO(n)にするには、私は今回は数値ではなく文字列を扱っているので、まず中央値を見つけようとするのではなくリストの中心にあるアイテムを中央値にする事にしました(O(1))。
またリストはm＋nではなくmのみにしようかと思います。
ただ、どうしても再起部分のnlognが残ってしまって、そこを解決する方法がまだ思いついていません。
よろしければヒントを下さりませんか？

補足日時：2014/11/07 03:35

No.4 回答者： nag0720 回答日時： 2014/11/06 16:30

＞m人の顧客を検索するのはO(m*1)でO(m)になる事はないのでしょうか？

計算量O( )の表記は、O(nの式)で表現します。
このnは「n人の名前リスト」のnとは全然関係ありません。

計算量が計算サイズに比例するとき、計算量のオーダーをO(n)と表記します。
計算量が計算サイズの２乗に比例するなら、O(n^2)と表記します。

m人だからと言って、O(m)と書くことはしません。この場合でもO(n)と表現します。


質問のはじめにあった「以下の問題をO(n)の時間で解くには、・・・」のO(n)のnは、契約更新した人数のことではありませんよ。単なるオーダーの記法です。

No.3 回答者： Tacosan 回答日時： 2014/11/06 00:26

あれ? 中央値を求めるアルゴリズムを流用してごにょごにょすればできるような気がする....

この回答への補足

回答どうもありがとうございます。

選択アルゴリズムの事でしょうか？
よろしければ、ごにょごにょ部分をもう少し詳しく教えて頂けると嬉しいです。
よろしくお願いします！

補足日時：2014/11/06 13:57

No.2 回答者： nag0720 回答日時： 2014/11/05 16:44

＞私は最悪O(mn)時間かかるのではないかと思ったのですが、

最悪というのはどういう場合でしょうか？
もしかして、ぜんぶ衝突した場合？
もしそうなら、それはハッシュ関数が最悪なだけですから、もっとましなハッシュ関数を作るしかないですね。


n人のハッシュテーブルを作成するのにO(n)、
ハッシュテーブルさえできればその検索のオーダーはO(1)です。
あとは、m人の顧客を検索するだけですからオーダーはO(n*1)＝O(n)
ということで、O(n)＋O(n)＝O(n)

この回答への補足

再度の回答をありがとうございます！

最悪というのは、ワーストケースの事を言っているつもりでした。
言葉足らずですみません。

m人の顧客を検索するのはO(m*1)でO(m)になる事はないのでしょうか？
O(n)＋O(m)だとO(m)になってしまうので、ハッシュテーブルでは出来ないという事になるんでしょうか。
ハッシュの知識があまりないので間違っていたら申し訳ありません。

補足日時：2014/11/06 14:02

No.1 回答者： nag0720 回答日時： 2014/11/05 15:13

ハッシュ法を使えばいいんじゃないの。

この回答への補足

ご回答ありがとうございます。
例えばm人分の顧客リストをハッシュテーブル化して、更新契約のきたn人分のハッシュテーブル内の数値を変えるとすると、私は最悪O(mn)時間かかるのではないかと思ったのですが、O(n)時間内に全てを終わらせる方法があれば詳しく教えて頂いても良いですか？

補足日時：2014/11/05 16:09