時間計算量 | サイズnの入力に対して出力が得られるまでの時間を表す関数f(n) |
空間計算量 | 時間計算量の時間を「メモリ」に置き換えて考えて表したもの |
平均計算量 | 全ての入力パターンに対し、それらの計算量を平均をとったもの |
最大計算量 | そのアルゴリズムにとって最悪のデータを使った場合の計算量 |
名称 | 処理内容 | 計算量 |
バブルソート | 配列の先頭から後ろに向かってスキャンし、隣り合う要素の大小関係が逆である場合は入れ替える整列アルゴリズム。 | O(n^2) |
選択ソート | 未整列の(整列されていない)部分から最小の要素を選び、それを未整列部分の先頭に移動させ、徐々に整列を行っていく整列アルゴリズム。 | O(n^2) |
挿入ソート | 配列の一部を整列済みとし、残りの要素を一つずつ、整列済みの部分の適切な位置に挿入していく整列アルゴリズム。 | O(n^2) |
ヒープソート | insert処理によって探索木を構築し、それに対してremoveMin処理を行っていき、要素を取り出していくことで整列を行う整列アルゴリズム。 | O(nlogn) |
マージソート | データ列を真ん中で半分に分けていき、それぞれの部分列で整列を行った後に合併(マージ)を行っていくことで整列を行う整列アルゴリズム。 | O(nlogn) |