2

この例のO（Log（N））を正確に計算する方法を知りたい：10個の要素のソートされた配列があります[1 3 4 8 10 15 18 20 25 30]通常の検索を行うと、次のような複雑さがあります。 O（10）は、配列のすべてのケースをチェックする必要があることを意味します。したがって、O（10）= 10です。ただし、並べ替えられた配列があるために二分検索を行うと、複雑さは（O（Log（10））になります。この表記の結果は何ですかO（Log（10））= ????私は誤解がありますログベース10または2を使用しますか、それとも正確には何ですか？助けてくれてありがとう

4

5 に答える 5

14

アルゴリズムの成長順序の概念を誤解しています。アルゴリズムに関する本を読んで、概念を強化してください。いずれにせよ、大まかに説明してみますが、

あなたが言ったように10個の要素の配列があり、「通常の検索」（線形検索と呼ばれます）を行う場合、配列内の各要素を反復処理します。つまり、「n」個の要素がある場合「n」個の要素チェックする必要があります。つまり、O(10) ではなく O(n) です。それが O(10) [ところで、O(10) = O(1) ] の場合、配列内に要素がいくつあっても、常に 10 回以下の反復が必要になることを意味しますが、そうではありません. 配列に 100 個の要素がある場合、100 回の反復が必要になるため、順序は O(n) であると言います。ここで、n は入力サイズ (ここでは配列のサイズ) です。

上記の方法は、ソートされていない配列用です。ソートされた配列の場合、辞書で単語を検索するのと同じように、より高速な検索方法を使用できます。この手法はバイナリ検索と呼ばれます。ここで何が起こるかというと、配列の中央の要素を調べて、探している数字が前半または後半のどこにあるかを確認します。次に、必要な半分を選択し、半分に分割して確認する同じ方法を適用します。これは再帰的に行われているため、対数成長を使用します (二分探索の場合は底が 2 の対数です)。理解を深めるために、二分探索と成長の対数順序を読んでください。

于 2013-02-23T18:56:50.040 に答える
7

二分探索がなぜ log(n) なのか、なぜ底が 2 なのか、あなたは混乱していると思います。このように考えてください。二分探索のすべてのステップで、入力サイズを 2 ずつ減らしています。何回必要ですか。これをする ？サンプル サイズを 1 に減らすには、この log n を基数 2 回行う必要があります。

たとえば、4 つの要素がある場合、最初のステップで検索が 2 に減り、2 番目のステップで検索が 1 に減り、停止します。したがって、log (4) を基数 2 に 2 = 2 回実行する必要がありました。つまり、log n base 2 = x の場合、2 の x 乗は n です。

したがって、バイナリ検索を実行している場合、ベースは 2 になります。より明確に、あなたの場合、Log(10) ベース 2 は約 3.3 になります。つまり、最大 4 回の比較を行うことになります。

于 2013-02-23T20:05:00.107 に答える
2

残念ながら、それは漸近法の仕組みではありません。Big-O 表記は、アルゴリズムが可変サイズの入力に対してどのようにスケーリングするかを説明することを目的としています。特に、固定入力 (上記のように) でアルゴリズムが必要とする操作の数は、常に定数、つまり O(1) になります。同様に、big-O 表記は定数の乗算に対して不変です。この意味は：

  • O(1) = O(10) = O(Log(10))
  • 底を変更すると定数係数のみが導入されるため、対数の底は重要ではありません
于 2013-02-23T18:51:43.703 に答える
1

Log base 10または2を使用するのか、それとも正確に何を使用するのか、誤解しています。

それはどうでもいい事です。複雑さは変わりません。ログベース2は次のものと同じです。

Log_2(N) = Log(N) / Log(2)

どちらもの要素ですO(Log(N))。

于 2013-02-23T19:19:15.387 に答える