Big-O Notation複雑度-ソート

アルゴリズム複雑度計算項目
1.時間複雑度:アルゴリズム実行速度
2.空間複雑度:アルゴリズムで使用するメモリサイズ
時間が大切だ.
タグアルゴリズムの最悪の実行時間.(パフォーマンスが最も低いことを示す)
時間複雑度の計算は反復文の影響が大きい.
入力nに基づいて計算を何回実行するかは、式に最も影響を与えるnの単位としてマークされます.
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ)
時間下限(最速)、時間上限(最速)

ソート方法とbigoタグ

過去に作成されたJavaScriptソートの実装:https://blog.naver.com/namju1v/222226455895

線形検索:O(n)

必要な要素を見つける前に、最初から最後まで順番に検索します.
線形探索アルゴリズムは正確だが効率が低い方法である.
線形検索は、ソートされていない場合や情報がない場合に便利です.
最大1回まで検索可能

バイナリナビゲーション:O(logn)

配列がソートされている場合は、配列の中央にあるインデックスから検索する値と比較し、小さい(小さい値を格納)インデックスまたは大きい(大きい値を格納)インデックスに繰り返し移動します.
最適な場合は1(中間数が見つかった)

泡の位置合わせ:O(n)²)

2つの隣接するデータ値を同時に比較する位置を交換します.
Bubbleソートは、2つの要素のみをソートする狭い範囲に集中します.
この方法は簡単ですが、単一の要素を揃えるために交換が多すぎて、これは無駄です.
位置合わせの有無にかかわらず、リングの周りで比較します.(上限/下限ともにn)²)
(交換が発生しない場合に停止する条件がある場合は、n回が望ましい)

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

ソート選択:O(n)²)

列の最小値(または最大値)を検索し、最初の位置(または最後の位置)の数と交換するソート方法.ソートを選択すると、交換回数を最小限に抑えることができますが、各材料を比較する回数が増加します.n²確認します.

For i from 0 to n–1

    Find smallest item between i'th item and last item

    Swap smallest item with i'th item

連結ソート:O(nlogn)

連結ソートは、1つの要素が1つの要素になるまで連続的に分割され、連結およびソートされます.
また,このプロセスは再帰的に実現される.
集計ソート実行時間の上限はO(n log n)である.
数字を半分に分けるにはO(logn)の時間が必要なので、半分に分けた部分を並べ替えて統合するにはO(n)の時間が必要です.運転時間の下限もΩ(n logn)である.数値がソートされているかどうかにかかわらず、分割とマージが必要です.

挿入位置合わせ:O(n)²)

最初から、自分を含めて、ソートを実行し、自分以外はすでにソート状態にあると仮定します.
エレメントの最後に、初期エレメントから終了エレメントまでのソートを実行します.
整列されている場合、O(n)であってもよい.

クイックソート:O(nlogn)

任意の値を基準にして、小さい値と大きい値に分けます.
このプロシージャは、最小単位でソートされるまで、小値部分、大値部分で繰り返し実行されます.
最終的にはn個の要素を分割する必要があり,これはO(n)の複雑さを意味する.
ただし,分割を繰り返すオブジェクトの規模が半分に減少したため,O(logn)を目指して実行する.
すなわちO(nlog n)複雑度を有する.
最悪の場合O(n)²)任意に抽出された数が要素の最小値または最大値である場合に、要素を不均衡に半分に分割する複雑さがある.分割の回数nは同じであり,比較対象はn−1,n−2程度に減少し,最終的にnをn回分割するのでO(n)²)はい.