- ベストアンサー
アルゴリズム:効率の良い探索方法
アルゴリズムに関する質問です。 以下の問題をO(n)の時間で解くには、どのような方法を使えばいいのでしょうか？ どうぞよろしくお願い致します。 【問題】 とある店でm人いる顧客のうち、n人から契約更新の届けが来ました。 店側から届けが来ていない顧客(m － n人)へ契約更新のお知らせを出したいのですが、店にはソートされていない顧客の名前リストと、こちらもソートされていない契約更新をしたn人の名前リストしかありません。 m＝nだった場合は”なし”と、m＞nだった場合は契約更新をしていない顧客の名前を一人分アウトプットとして返しなさい。
- mugiNoumi
- お礼率28% (2/7)
- 情報工学
- 回答数7
- ありがとう数13
- みんなの回答 （7）
- 専門家の回答
質問者が選んだベストアンサー
#2, #4です。 失礼しました。とんでもない勘違いをしてました。#4は間違いです。無視してください。 で、m人の顧客の検索がO(n)であるという理由ですが、 m＞nだとして、m人のうちn人だけを検索します。 そのなかに１人でもハッシュテーブルにない顧客がいれば、それをアウトプットすればいい。 もしn人全員がハッシュテーブルに存在したとすれば、残りの顧客(m-n人)はすべて契約更新していないのだから、その中から適当に１人を選んでアウトプットすればいい。 いずれにしても、m人全員を検索する必要はなく、多くともn人の検索で充分なのでオーダーはO(n)になります。
その他の回答 (6)
- Tacosan
- ベストアンサー率23% (3656/15482)
残念ながら外れ. 大きな間違いは, 再帰の部分で計算量を nlogn としちゃってるところ. 確かに最悪 O(log n) 回の再帰が必要だから全体で O(n log n) となりそうなんだけど, 再帰をするごとにリストが短くなることを考慮して計算し直せばきっちり線形時間で終らせることができる. 解析は選択アルゴリズムと本質的に同じなので, 疑問に思ったら確認してみるといい (ただし Wikipedia の説明はちょっと日本語がこなれてないので読みにくいかも). あとは細かいところで ・リスト全体の中央値を使うかわりにリストのまんなかにある値を使うと最悪の場合に計算量が大きくなるのでダメ (ここも本質は選択アルゴリズムと同じ: ここで線形時間使っても, アルゴリズム全体の時間は線形時間のまま) ・リストを m にすることに意味はない (リストの長さを 2n+1 にすることができる, というのは #6 の説明の通り) というところかな. あ, もちろん「想定する答え」は「ハッシュ」だと思うよ. というか, ハッシュ以外のアルゴリズムを想定するかなぁ, ふつう....
お礼
お礼を申し上げるのが大変遅くなってしまい、申し訳ございません。 ゆっくり時間をかけて考え、計算したところ、Tacosan様がおっしゃっていたように線形時間で終わるアルゴリズムを作る事が出来ました。 細かい部分まで丁寧に説明して下さってどうもありがとうございました。 とても説明が分かりやすく、アルゴリズムが苦手な私にとっては大変ありがたかったです！
- Tacosan
- ベストアンサー率23% (3656/15482)
確認だけど, 「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が残ってしまって、そこを解決する方法がまだ思いついていません。 よろしければヒントを下さりませんか？
- nag0720
- ベストアンサー率58% (1093/1860)
＞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は、契約更新した人数のことではありませんよ。単なるオーダーの記法です。
- Tacosan
- ベストアンサー率23% (3656/15482)
あれ? 中央値を求めるアルゴリズムを流用してごにょごにょすればできるような気がする....
補足
回答どうもありがとうございます。 選択アルゴリズムの事でしょうか？ よろしければ、ごにょごにょ部分をもう少し詳しく教えて頂けると嬉しいです。 よろしくお願いします！
- nag0720
- ベストアンサー率58% (1093/1860)
＞私は最悪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)になってしまうので、ハッシュテーブルでは出来ないという事になるんでしょうか。 ハッシュの知識があまりないので間違っていたら申し訳ありません。
- nag0720
- ベストアンサー率58% (1093/1860)
ハッシュ法を使えばいいんじゃないの。
補足
ご回答ありがとうございます。 例えばm人分の顧客リストをハッシュテーブル化して、更新契約のきたn人分のハッシュテーブル内の数値を変えるとすると、私は最悪O(mn)時間かかるのではないかと思ったのですが、O(n)時間内に全てを終わらせる方法があれば詳しく教えて頂いても良いですか？
関連するQ&A
- アルゴリズム
アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。 ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。 (1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。 解) n=100*2 =200 (2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。 解) 求める問題の大きさをxとおくと n=(100^2)*100 =10000*100 =1000000 (3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。 解) 2^40=(2^20)*(2^20) =1*(2^20) =2^20[時間]
- ベストアンサー
- その他（プログラミング・開発）
- アルゴリズムについて
大学の授業の課題のアルゴリズムについてなのですが、内容的に頭がついて行けず、一切分かりません。問題内容は、最小値を求めるアルゴリズム（必要な箇所を修正して下さい）です。 どなたか詳しい方いらっしゃいますでしょうか？ よろしくお願いいたします。 M = -9999 データX入力 while X ≠ 9999 Y M < X N M = X データX入力 Mを出力
- 締切済み
- 情報処理技術者
- アルゴリズム系の問題知りませんか？
再来週大学院試験を控えている者です。 入試の項目に「プログラミング(アルゴリズム)」と書いてあり、ある程度複雑なアルゴリズムを考えるような問題が出る事が予想されます。 きっと二分探索木やクイックソートのような問題が出るように思います。 アルゴリズムを考えるような問題としていい問題ご存じないでしょうか？ アルゴリズムを考えるような問題としてはハノイの塔とかよいように思いますが ちょっと入試の問題としては出ないような気がします。 自分では他に線形リストやスタックなども勉強したんですが、 C,JAVA,Pascal,フォートランなどどの言語で回答してもよい事になっているので言語に限定した問題は出ないように思います。 90分で解く３問あるうちのプログラムは１つですから30分以内に解けるような問題のはずです。 (出題される可能性も考えていただければ幸いです)よい問題をご存知でしたら教えてください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 経路探索の問題
http://www.i.u-tokyo.ac.jp/edu/course/m-i/pdf/2002imim.pdf の、問題3について質問なのですが、 問1は、 (1) 線形リストとして、n回で到達できるセルの情報を与えると、n+1回で到達できる線形リストを返す関数を考える。返すリストの作成方法は、n回で到達できるセルの前後左右を調べて、すでに調べたセルや障害物のセルでなければ、そのセルをn+1回で到達できるセルとしてメモし、返す線形リストに追加する。 (2) int l[M][N];//特定のセルまでの距離をメモする配列。最初にすべて-1をいれておく。障害物には-2を入れておく。 class list{ int i,j; list *next; list(){ next=0; } } //n回で到達できるセルのリストをpl、n+1階で到達できるセルのリストを返すポインタをnlとする。 void getNextCellsList(list *pl,list *nl){ list *tt=pl; list *t; int i,j; nl=0; while(tt){ i=tt->i; j=tt->j; if(i>0&&l[i-1][j]==-1){ l[i-1][j]=l[i][j]+1; t=nl; nl=new list; nl->i=i-1; nl->j=j; nl->next=t; } if(j>0&&l[i][j-1]==-1){ l[i][j-1]=l[i][j]+1; t=nl; nl=new list; nl->i=i; nl->j=j-1; nl->next=t; } if(i<M-1&&l[i+1][j]==-1){ l[i+1][j]=l[i][j]+1; t=nl; nl=new list; nl->i=i+1; nl->j=j; nl->next=t; } if(j<N-1&&l[i][j+1]==-1){ l[i][j+1]=l[i][j]+1; t=nl; nl=new list; nl->i=i; nl->j=j+1; nl->next=t; } tt=tt->next; } } と、したのですが、このgetNextCellsList関数を一回使う時間計算量は、O(n)としていいのでしょうか？ また、もしそうなら問2の時間計算量は、 (getNextCellsList関数を一回使う時間計算量)*M*N=O(n)*O(n^2)=O(n^3) 空間計算量は、 (セルまでの距離をメモする配列の数)+(n回で到達できるセルの情報)=O(n^2)+O(n)=O(n^2) となるのでしょうか？ あと、この問題の(M,N,D)のオーダーで評価せよというのはどういう意味として捉えればいいのでしょうか？O(n^3)などと書いておくだけで良いのでしょうか？ 問3の時間的及び空間的に効率化する方策としてはどのようなものが考えられるのでしょうか？これは、自力では全然ろくな方法が思い付きませんでした。。。 宜しくお願いします。
- ベストアンサー
- C・C++・C#
- 剰余の法が大きい場合のアルゴリズム
プログラミング等でよく"x^n(mod m)を解け"といった問題がよく挙がりますが、法"m"が 大きい場合については触れているものが少ないので質問させていただきます。 例えば単純に除法で求める場合、"x^n"については展開できるので、何でもよい数として 簡単に"x"とおくと、"x/m"をニュートン法で求め"x-round(x/m)*m"で余を求める、という ような感じになります。ここで"m"は"1024bit"程度の大きい数を想定しています。よい アルゴリズムがあれば教えてください。
- 締切済み
- その他（プログラミング・開発）
- アルゴリズムによる整列方法について
以下の問題を授業外課題として出されましたがわかりません。身近に分かる人物もいません。 先生も答えてくれません。 解答お待ちしております。 １．以下の文章の空欄を埋めよ．但し，((14)),((15)) については，選択肢から最も適切なものを選び，記号で答えよ．加えて，解答の過程を詳しく述べよ。 高速な整列として以下のアルゴリズムによる方法を考える．以下では，整数データを昇順に配列するも のとする． 前段階として，データを半々に二つのグループ I と II に分割し，それぞれを独立に整列する． while (両グループに要素が残っている) do if (グループ I の最小要素 < グループ II の最小要素) then グループ I の最小要素を出力場所に移し，グループ I からは削除する else グループ II の最小要素を出力場所に移し，グループ II からは削除する endif done while (グループ I に要素が残っている) do グループ I の要素を出力場所に移し，グループ I からは削除する done while (グループ II に要素が残っている) do グループ II の要素を出力場所に移し，グループ II からは削除する done この整列に要する計算量 T(n) を求める．但し，n は整列するデータの量である．前段階の整列では，半分のデータ量の整列を 2 回行うので ((1)) だけの計算を要する．次に，3 個の while 反復のいずれについても， 「反復を 1 回行うごとに要素が一つだけ出力場所に移動する」 ことから，3 個を合計すると反復の中身は正確に ((2)) 回実行されることが分かる．1 回の実行に a だけの時間がかかるものとすれば，全体で ((3)) となる．従って次の関係式が成り立つ． T(n) = ((4)) 簡単のため，n = 2^p であるとすると， T(n) = ((5))×T(2^((6)) ) + ((7)) = ((8)) × T(2^((9)) ) + 2 × ((7)) ・ ・ ・ = ((10)) × T(2^0) + ((11)) T(2^0) = ((12)) なので，T(n) を a と n のみを用いて表すと， T(n) = ((13)) であり，これは， ((14)) に比例し，計算量のオーダーは ((15)) といえる． ((14)),((15)) の選択肢 a. n b. n^2 c. 2^n d. n log n e. log n f. いわゆる「指数オーダー」であり，アルゴリズムとして全く実用に耐えない g. いわゆる「バカソート」と同じであり，n がごく小さい場合を除いて実用には適さない h. 経験上最速とされるソート法には及ばないが，それほど大きくない n に対しては実用に耐える i. 経験上最速とされるソート法と同じであり，十分大きい n に対しても実用に耐える
- 締切済み
- 数学・算数
- 経路探索
よろしくお願いします。 現在経路探索問題のプログラムを書いています。 そこでわからない点があったので教えてください。 以下のような(n行,m列)の経路があります。 (0,0)－(0,1)－(0,2)－(0,3) (1,0)－(1,1)－(1,2)－(1,3) (2,0)－(2,1)－(2,2)－(2,3) (3,0)－(3,1)－(3,2)－(3,3) (4,0)－(4,1)－(4,2)－(4,3) スタートを(4,3)としてゴール(0,0)にたどり着く全ての経路を求めたいです。 条件としてある点から 左(例えば(4,3)⇒(4,2)) 上(例えば(4,3)⇒(3,3)) 斜め(例えば(4,3)⇒(3,2)) にしか進むことはできません。 このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？ ご解答要路しくお願いします。
- ベストアンサー
- C・C++・C#
- 流れ図について
「自然数m,nに対して、mのn乗を計算する効率のいいアルゴリズムを流れ図を記述せよ（n＝６４のとき、乗数の回数は６回ですむ）」って問題がでたのですが答えられずわからなかったのですが、効率のいいアルゴリズムを流れ図で書くことはできるのでしょうか？宜しくお願い致します。
- 締切済み
- その他（プログラミング・開発）
- マージソートの計算量
データ構造とアルゴリズムのテストでこんな問題が出てきました。 マージソートにおける値の比較回数は、C(n)は次のように表すことができる。C(4)は幾らか。 C(n) = 1 (n = 1のとき) C(n) = 2 C(n/2) + n (n > 1のとき) この問題の解答は１２でした。 この問題を解くプロセスを教えていただけませんか？ よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
お礼
お礼を申し上げるのが大変遅くなってしまい、申し訳ございません。 nag0720様のおかげでどうしてハッシュテーブルを使えばO(n)時間で探索が完了出来るのか分かるようになりました。 丁寧に回答して下さって、感謝してもしきれません。 本当にありがとうございました！