1

n 個の要素の配列があります。それらの要素は数字です。私が今しなければならないことは、私の配列でそれらをたくさん見つけることです。sqrt(n)私は検索についてしなければならないでしょう。

効率の観点から、私にとってより良いオプションは何ですか?

  1. 線形検索
  2. 配列の並べ替え (線形時間で言えば、たとえば RadixSort を使用すると可能です) し、二分探索で要素を検索します -O(logn)

私はいくつかの直感を持っていますが、それを確認して証明する方法がわかりません。線形探索のコストは (最悪の場合) : O(n) * O(sqrt(n)) です。ソート後の二分探索はO(n) + O(logn) * O(sqrt(n)).

4

2 に答える 2

1

問題を解決するには、次の 2 つの方法があります。

  1. 並べ替えてから検索する
  2. 検索するだけ

複雑さの表を作成すると、解決策が得られます。おそらく、このhttp://rechneronline.de/function-graphs/のようなツールを使用して、2 つの複雑さを比較できます。

あなたが持っているさまざまなケース：

  1. sqrt(n) 回の線形検索 = O(n * sqrt(n))。
  2. 線形ソートと二分探索 sqrt(n) 回 = O(n) + O(log(n) * sqrt(n)= O(n)

2番目が最も有望なようです。

于 2013-01-13T16:50:21.867 に答える
1

あなたが言ったように、あなたには2つの選択肢があります：

  1. 線形検索sqrt(n)時間。費用はO(n * sqrt(n))です。
  2. 配列を並べ替えてO(n)から二分探索するsqrt(n)。
    費用はO(n + log(n) * sqrt(n))です。はすべて正のn場合よりも大きくなります。 証明。 これのおかげで、私たちは書くことができます。 ソート部分が支配的で、それがボトルネックです。log(n) * sqrt(n)n
    O(n + log(n) * sqrt(n)) = O(n)

そのため、 big の 2 番目のアプローチはn高速で、ほぼ線形です。

于 2013-01-13T16:44:19.147 に答える