複雑さがO（n^3）のソートアルゴリズムは良いか悪いですか？

Question

O(n^3)のようなソートアルゴリズムの難易度はどうやって確認できますか？

どのような種類の問題がありますか？どのように私はそれらを読んで/理解するのですか？

さまざまなウェブサイトにアクセスしようとしましたが、どのコードに難易度があるのか​​、どんな複雑さが良いのか悪いのかわかりませんでした。

ありがとうございました。

Answer 1

非常に悪いです。バブルソートでさえも複雑さはO（n^2）です。すべてのアルゴリズムは完了するためにいくつかの操作を行う必要があります。また、演算回数を減らして実現すれば、アルゴリズムは優れています。たとえば、検索の場合、配列のすべての項目（ソートされていない）をチェックする必要があります。最悪の場合は、項目をチェックする必要があります。したがって、このアルゴリズムの複雑さはnです。アルゴリズムがa1 * n^x1 + a2 * n^x2 + ... + an * n^xn演算（x1> x2> ...> xn）の場合、そのアルゴリズムの複雑さはO（n^x1）
実際にはcmplexityの場合、3つの分類があります：最悪、平均、最善。 thisを読むと参考になります。

Answer 2

http://thomas.baudel.name/Visualisation/VisuTri/algorithms.html

たぶんそれを読んすることはあなたのアイデアを提供します。あなたのヘッダーはテキスト本文とは異なる情報を含んでいます。 O（n^3）は確かに悪いです。最適なソートアルゴリズムは、周囲の領域にあります。O（n * log（n））

Answer 3

ソートの場合、O(n^3)は良くありません。素朴なソートアルゴリズムでさえ、それよりもうまくいく可能性があります。しかし、ソート以外の他の処理を行うアルゴリズムでは、多項式時間の複雑さを考えると、O(n^3)はうまくいくかもしれません。

Answer 4

O（n^3）はソートアルゴリズムにとって非常に複雑ではありません。これは、ソートアルゴリズムは、例では3つのネストされたループを有すること、を意味する：あなたの配列は100個の要素を持っている場合実際に

for (int i=0; i< n; i++) { 
    for (int j=0; j< n; j++) { 
     for (int k=0; k< n; k++) { 
      do_something(i, j, k); 
     } 
    } 
} 

を、ソートはループthrought 1つの000 000パスをとります。

より良いアルゴリズムはO（n^2）の複雑さを持ち、例O（n log（n））（ヒープソートのような）ではO（n^1）に近い。

Answer 5

• 最高のソーティング時間は、範囲がわかっていれば線形です。
• アイテムを比較する並べ替えは、ツリー構造のように広がっているため、ランタイムnlognを最適な状態にすることができます。ここで
  はあなたが表示されます主なもののリストです：

は、あなたが大きなO記法についての詳細を学ぶ必要があると思われます。 o（1）、o（log（n））、O（n）、nlogn、n^2、logn * n^2、n^3、logn * n^3などがベストでしょう...私はあなたがそのパターンを見ることを願っています。

Answer 6

すべて深刻なソートアルゴリズムはが上限示しはO（n^3）としてはO（n^3）複雑さを有します。マージソートはO（n log n）の最悪の場合の複雑さを持っています。つまり、最悪の場合のランタイムは、並べ替える要素数が直線よりも少し速くなる場合があります。O（n^3）は、最悪の場合のランタイムが非常に速い立方体に成長する可能性があることを意味します。しかし、O表記は上限です。これは、最悪の場合のスケーリングの振る舞いが3次よりも悪くないことを示すことができます。 [1つまたは2つ以上のステップ...]したがって、O（n log n）にあるものは、O（n^3）にあります。

非コンピュータ科学者のために、本「Algorithm Design Manual」には、いわゆるBig-O表記の簡単な紹介と動機が含まれています。 lectures notes based on the bookがあります。