19

私は現在、Big Oh の基本的なアルゴリズムを研究しています。Big Oh を使用した Java の (n log n) のコードがどのようなものかを誰かに教えてもらえないかと思っていました。

私は初心者なので、書く前にコードを想像することしかできません。したがって、理論的には (少なくとも)、n 回の for ループを 1 つ含める必要があります。次に、log n に対して、while ループを使用できます。したがって、ループは n 回実行され、while ループは log base 2 回実行されます。少なくともそれが私の頭の中で想像している方法ですが、コードを見ると問題が解決します。

4

4 に答える 4

57 
int n = 100
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n)
{
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times
    {

    }
}

説明: 外側の for ループはクリアする必要があります。回実行されnます。では内側のループへ。内側のループではn、常にそれを で割り2ます。それで、あなたは自問します: で何回割ることができnます2か?

これは であることがわかりO (log n)ます。実際、 の基数はlogです2が、Big-O 記法では基数を削除しlogます。これは、興味のない要素を私たちに追加するだけだからです。

したがって、ループn回を実行しており、そのループ内で別のループlog(n)回を実行しています。だから、あなたは持っていO(n) * O(log n) = O(n log n)ます。

于 2013-09-26T06:52:17.050 に答える
5

非常に一般的な O(n log n) アルゴリズムは、マージ ソートです。http://en.wikipedia.org/wiki/Merge_sortアルゴリズムと疑似コードの例。アルゴリズムの log n 部分は、問題をより小さな部分問題に分割することによって達成されます。再帰ツリーの高さは log n です。

多くのソートアルゴリズムの実行時間は O(n log n) です。その他の例については、 http://en.wikipedia.org/wiki/Sorting_algorithmを参照してください。

于 2013-09-26T06:48:42.277 に答える
4

O(.)を含む時間の複雑さを持つアルゴリズムには、log n通常、何らかの形式の分割統治が含まれます。

たとえば、MergeSort では、リストが半分に分割され、各部分が個別にマージソートされてから、2 つの半分がマージされます。各リストは半分になります。

作業のサイズが一定の係数で半分または縮小されるときはいつでも、通常は のlog nコンポーネントになりO(.)ます。

コードに関しては、MergeSort のアルゴリズムを見てください。TopDownSplitMerge典型的な実装の重要な機能は、それが再帰的であることです (ウィキペディアで提供されているコードでは、自分自身を 2 回呼び出すことに注意してください)。

すべての優れた標準的な並べ替えアルゴリズムにはO(n log n)時間の複雑さがあり、最悪の場合にはそれを改善することはできません。比較並べ替えを参照してください。

これが Java コードでどのように表示されるかを確認するには、検索してください ! ここに一例があります。

于 2013-09-26T06:53:49.937 に答える
2

http://en.wikipedia.org/wiki/Heapsort

簡単な例は、あなたが説明したとおりです-log（n）時間かかる操作をn回実行します。バランスの取れた二分木には log(n) の高さがあるため、一部のツリー アルゴリズムはこのように複雑になります。

于 2013-09-26T06:49:35.420 に答える