4

これは、G。MichaelScneiderとJudithL.Gerstingによる教科書InvitationtoComputerScienceからの直接の引用です。

セクション3.4.2の最後で、リストをソートしてからバイナリ検索を使用するのではなく、ソートされていないリストで順次検索を使用することのトレードオフについて説明しました。リストのサイズがn=100,000の場合、比較の数の点で2番目の選択肢が優れている前に、最悪の場合の検索を何回実行する必要がありますか？

質問が何を求めているのか、私にはよくわかりません。

シーケンシャル検索は次数（n）で、バイナリは次数（lgn）であり、いずれの場合もlgnは常にn未満になります。そしてこの場合、nはすでに与えられているので、私は何を見つけることになっています。

これは私の宿題の1つですが、どうしたらよいかわかりません。誰かが私のために平易な英語で質問を説明できますか？

4

6 に答える 6

7

バイナリは次数（lgn）であり、いずれの場合もlgnは常にn未満になり
ます。これは間違いです。割り当てでは、配列の並べ替えのコストも考慮するように求められます。

明らかに、検索が1つだけ必要な場合は、配列を並べ替えてバイナリ検索を実行するよりも、最初のアプローチの方が適していますn < n*logn + logn。そして、2番目のアプローチをより効果的にするために必要な検索の数を尋ねられます。

ヒントの終わり。

于 2010-10-20T10:46:51.037 に答える
3

問題は、どのアプローチを選択するかを決定する方法です。線形検索を使用するか、並べ替えてからバイナリ検索を使用するかです。

数回だけ検索する場合は、線形検索の方が適しています。これはO（n）ですが、並べ替えはすでにO（n * logn）です。同じコレクションで頻繁に検索する場合は、並べ替えの方が適しています。複数回検索するとO（n * n）になる可能性がありますが、並べ替えてからバイナリ検索で検索すると、再びO（n * logn）+ NumberOfSearches * O（logn）になります。 NumberOfSearchesとnの関係に応じて、線形検索を使用するよりも少ないまたは多い。

タスクは、NumberOfSearchesの正確な値（正確な数ではなく、nの関数）を決定することです。これにより、オプションの1つが望ましいものになります。

 NumberOfSearches * O(n) <> O(n*logn) + NumberOfSearches * O(logn)

各O（）は異なる定数値を持つことができることを忘れないでください。

于 2010-10-20T10:46:13.617 に答える
1

ここでは、メソッドの順序は重要ではありません。問題がますます大きくなるにつれて、アルゴリズムがどれだけうまくスケールするかがわかります。O(n)== 複雑さが問題のサイズに比例して増加することだけを知っている場合、正確な計算を行うことはできません。それはあなたに数字を与えません。

これは、O(n)複雑なアルゴリズムがアルゴリズムよりも高速であることを意味する可能性がありO(logn)ます。O(log(n)) は大きくなるほどスケーリングが向上するためn、O(logn) の複雑さを持つアルゴリズムが高速になる (問題のサイズ) があることは確かです。いつ（何のために）わからないだけですn。

平易な英語で：

「検索回数」を知りたい場合は、解くための正確な方程式が必要であり、正確な数が必要です。順次検索するのに何回の比較が必要ですか? (n が与えられているので、数字を与えることができることを思い出してください。) 二分探索で検索するには、何回の比較 (最悪の場合でも!) が必要ですか? 二分探索を行う前に、ソートする必要があります。ソートに必要な比較の数を二分探索のコストに追加しましょう。では、2 つの数値を比較して、どちらが小さいでしょうか?

二分探索は高速ですが、ソートは低速です。順次検索は二分検索よりも遅くなりますが、ソートよりは高速です。ただし、検索回数に関係なく、並べ替えは 1 回だけ実行する必要があります。では、毎回遅い (シーケンシャル) 検索を実行する必要がある 1 つの重い並べ替えが、どのような場合に勝るでしょうか?

幸運を！

于 2010-10-20T11:58:34.397 に答える
0

問題はNUM_SEARCHES、仕分けのコストを補うために必要な数を評価することです。したがって、次のようになります。

 time( NUM_SEARCHES * O(n) ) > time( NUM_SEARCHES * O(log(n)) + O(n* log(n)) )
于 2010-10-20T10:52:12.807 に答える
0

君たちありがとう。私は今ポイントを得たと思います。私の答えを見て、私が正しい方向に進んでいるかどうかを確認していただけますか。

ワースト ケース検索の場合 順次検索の比較回数は n = 100,000 です。二分探索の比較回数は lg(n) = 17 です。ソートの比較回数は (n-1)/2 * n = (99999)(50000) です。（私は教科書に従っており、クラスで説明されている選択ソートアルゴリズムを使用しています）

最悪の場合の検索回数を p とすると、100,000p > (99999)(50000) + 17p
OR p > 50008 となります。

結論として、n=100,000 のリストの順次検索よりも優れた並べ替えとバイナリ検索の使用を行うには、50,008 回の最悪の場合の検索が必要です。

于 2010-10-20T18:38:48.860 に答える