アルゴリズムの効率は、次の 2 つのパラメータによって決まります。
- 時間計算量
- 空間の複雑さ
時間計算量:
時間複雑さは、かかった合計時間ではなく、特定の命令セットが実行される回数として定義されます。所要時間の合計は、使用するコンパイラー、プロセッサの速度などの外部要因にも依存するためです。
空間の複雑さ:
スペース複雑度は、プログラムの実行に必要なメモリ スペースの合計です。
どちらも入力サイズ(n)の関数として計算されます。ここで重要なことの 1 つは、これらのパラメーターにもかかわらず、アルゴリズムの効率は、 自然 そして のサイズ の 入力。
時間計算量の種類:
- 最高の時間計算量: アルゴリズムにかかる時間が短い、または最小時間がかかる入力を定義します。最良の場合は、アルゴリズムの下限を計算します。例: 線形検索では、検索データが大きなデータの最初の位置に存在する場合、最良のケースが発生します。
- 平均時間計算量: 平均的なケースでは、すべてのランダムな入力を取得し、すべての入力の計算時間を計算します。
次に、それを入力の合計数で割ります。 - 最悪の時間複雑さ: アルゴリズムに長時間または最大時間がかかる入力を定義します。最悪の場合、アルゴリズムの上限を計算します。例: 線形検索では、検索データが大きなデータの最後の位置に存在する場合、最悪のケースが発生します。
以下は、直前に参照できる簡単な改訂シートです。
| アルゴリズム | 時間計算量 | 空間の複雑さ | ||
|---|---|---|---|---|
| 最高 | 平均 | 最悪 | 最悪 | |
| 選択範囲の並べ替え | の上2) | の上2) | の上2) | ○(1) |
| バブルソート | の上） | の上2) | の上2) | ○(1) |
| 挿入ソート | の上） | の上2) | の上2) | ○(1) |
| ヒープソート | O(n log(n)) | O(n log(n)) | O(n log(n)) | ○(1) |
| クイックソート | O(n log(n)) | O(n log(n)) | の上2) | の上） |
| マージソート | O(n log(n)) | O(n log(n)) | O(n log(n)) | の上） |
| バケットソート | O(n +k) | O(n +k) | の上2) | の上） |
| ソート基数 | O(nk) | O(nk) | O(nk) | O(n + k) |
| カウントソート | O(n +k) | O(n +k) | O(n +k) | 矢印） |
| シェルソート | O(n log(n)) | O(n log(n)) | の上2) | ○(1) |
| ティム・ソート | の上） | O(n log(n)) | O(nlog(n)) | の上） |
| ツリーソート | O(n log(n)) | O(n log(n)) | の上2) | の上） |
| キューブソート | の上） | O(n log(n)) | O(n log(n)) | の上） |
また、以下も参照してください。
- 記事の検索と並べ替え
- 前年度の GATE 並べ替えに関する質問
- 挿入ソートの時間と空間の複雑さ
- 選択ソートの時間と空間の複雑さ
- バブルソートの時間と空間の複雑さ
- クイックソートの時間と空間の複雑さ
- マージソートの時間と空間の複雑さ
- 基数ソート アルゴリズムの時間と空間の複雑さ