こんにちは。技術チームの李です。
先日馮さんによる「ソートアルゴリズムと複雑度解析」勉強会の内容を共有したいと思います。
1.Big O 複雑度解析
まずアルゴリズムの複雑度解析にあたって、Big O 複雑度解析を紹介します。
Big O 複雑度解析では、データのサイズを n とすると、アルゴリズムの処理時間を O(f(n)) と表すことができます。ここで、f(n) は、n に対する関数であり、アルゴリズムの処理時間がどのように変化するかを表します。
例えば、O(1) のアルゴリズムは、データのサイズに関係なく常に同じ時間で処理が終わるアルゴリズムを指します。一方、O(n) のアルゴリズムは、データのサイズが n 倍になると、処理時間も n 倍になるアルゴリズムを指します。
O(n^2)は、プログラムの実行時間が入力データのサイズの二乗に比例して増加することを意味します。
O(log n)は、プログラムの実行時間が入力データのサイズをlog(n)で割った値に比例して増加することを意味します。
あるプログラムの処理時間をT(n)としたとき、そのプログラムの複雑度は次数に依存する。
データが大きくなるにつれて処理時間の変化をグラフにした場合
処理時間が指数的に増加するとかなり恐ろしいことになります。
2.ソートアルゴリズムの正確性と安定性
正確性は、ソートアルゴリズムが正しく並べ替えることを意味します。 例えば、数値の昇順に並べるアルゴリズムは、すべての数値が正しく並び替えられていることを確認することで、正確性を検証することができます。
安定性は、同じ値を持つ要素が元の並び順と同じ順序で並んでいるかどうかを示すものです。
代表的なソートアルゴリズムは正確性は保証されていますが、安定性はどうでしょうか？
・バブルソート 安定性がある
・選択ソート 安定性がない
・挿入ソート 安定性がある
・所感
久しぶりにこれほど考えて、とてもいい頭の体操になりました。
コーディング時も、二重以上のループ使うとしたら、一旦もっといい方法ないか考えるべきだと思いました。
