algorithm - バブル、挿入、および選択の並べ替えに同じ Big-O があるのはなぜですか?

Question

タイトルが尋ねるように、挿入、バブル、および選択の並べ替えが同じ大物を持っているのはなぜですか? 私のアルゴリズム クラスでは、上記のアルゴリズムとマージ ソートの 4 つのアルゴリズムについて説明しましたが、なぜマージ ソートの代わりに上記のアルゴリズムを使用するのでしょうか?

Answer 1

これらは異なるアルゴリズムですが、あるレベルでは各アルゴリズムが長さ n のリストを 2 回通過するため、漸近的な複雑さは同じです。重要なのは、Big-O が最悪の場合のパフォーマンス測定値であるということです。挿入ソートは、最悪の場合O(n^2)ですが、最良の場合、リストがすでにソートされている場合はO(n)になります。さまざまな並べ替えアルゴリズムにはさまざまな長所があり、複雑さを超えた分析が必要です。

そうは言っても、ほとんどの場合、nlog(n) ソートを使用する方が適切であり、バブル ソートなどの主な機能は、おそらくソート アルゴリズムの概念を人々に紹介することです。

Answer 2

バブル ソートなどの一部のソート アルゴリズムは、アイテム数が多い場合は非常に遅くなりますが、アイテム数が少ない場合は非常に高速です。バブル ソートまたは挿入ソートは、アイテムが正しい位置にすでに近づいている場合にも役立ちます。多くの場合、優れた並べ替えアルゴリズムでは、ある手法を使用してアイテムをコース スケールで並べ替え、次に別のアルゴリズムを使用して詳細な並べ替えを行います。

Answer 3

これは、ここでよく尋ねられる質問の 1 つです。Big-O 表記法は、アルゴリズムの理論的な境界を測定する方法です。これは、最良の場合、一定の時間 O(1) であることが得られる場所です。これはめったに起こらないため、最良の場合です。これら 3 つのアルゴリズムが同じ大きな O を持つ理由は、それらがすべて同じ方法でソートの問題に取り組むためです。プロセスは似ています。純粋に学問的な観点から、これらが教えられる理由は、歴史から学び、バブルソートを考え出すことで「世界に衝撃を与える」とは思わないようにするためです. また、単純な概念のように見えるものがどのように見えるかを示すためにも使用されます。