計算量とソートアルゴリズム
計算量とソートアルゴリズム
今Think Complexity
chap3)で勉強した
について簡単にまとめを行いたいと思います． Think Complexity は無料で読む事もできます！
Analysis of algorithms(アルゴリズムの解析)
アルゴリズムの解析とはアルゴリズムの実行とメモリ消費を調べる分野です． 目標はプログラムを設計する時の目安として異なったアルゴリズム の実行効率を予測することです．利用するアルゴリズム・データ構造（データ構造によっても計算量にかなりの影響を与えます）の効率が悪ければ非常に遅くなりユーザにストレスを与える事になりかねます．
アルゴリズムの比較ではBig O notation(ビックO記法) と呼ばれる記法を用いて比較することが一般的です．また計算量を求める際は最悪の入力データを想定します．これを worst-case complexity（最大計算量）と呼びます．
しかしながら，実際に使用する場合には計算量が優秀だからといって それが適しているとは限りません．
例えば，
T1 = 10000n -> O(n)T2 = n^2 -> O(n^2)
この場合，小さい入力nに対してはT2の方が優秀です．もちらんnが大きくなるとO(n)の方が優秀です．したがって係数も意識する事も時には大切になります．実際の設計では係数も考慮した方が良い場合もあります．コーディングしてみて処理が遅いのであれば
profilerなどのツールを使ってリファクタリングすると良いでしょう．pythonであれば，python -m cProfile python_script.pyでpython_script.pyにある関数，クラス，メソッドの実行速度，呼ばれる回数などをプロファイリングする事ができます．
ソートアルゴリズムについて
多くのソートアルゴリズムはcomparsion sort（比較ソート）
です．comparison sortとは探索の対象となる要素の
大小を比較して，その結果によって要素の交換を行うアルゴリズムです．
ソートアルゴリズムと言えばこれをさす事が多いです．
また要素の数をnとしたときの最も高速なアルゴリズムでの計算量は
O(nlog(n))です．これは証明されているそうです．
（理解するのを放棄しましたので，説明はしません）
pythonのlistをソートする際のソートアルゴリズム(list.sort())には
stable(安定)なTimSort
が使われおり，cでは不安定(unstable)なクイックソートがqsortとして利用されています．ちなみに，ソートアルゴリズムの中で一番遅いソートの１つは
Bogosortです．
ソートには他にもnon-comparison sortというのがあります．
これは比較を行わないアルゴリズムで，
要素の特別な性質を使用します．要するに，事前条件が必要になります．比較ソートのように常に適応できるわけではありませんが，非常に高速（O(n)）なアルゴリズムです．
例）radix sort（基数ソート），Bucket sort（バケットソート）
stable sort(安定ソート)
先程説明したソートアルゴリズムでも出てきたstable（安定），unstable（不安定）について説明します．
例えば，ソートするデータのなかに同一の要素をもつレコードが 2つ以上含まれているとします．このデータをソートしたときに 同一の要素をもつデータ間で，ソート前の位置関係が保たれるような アルゴリズムの事をstable(安定)であると言い，そのようなソート アルゴリズムをstable sort（安定ソート）と呼びます．
反対に，ソートする事でソート前の位置関係が崩れるようなソートをunstable(不安定)と呼びます． 不安定ソートは実用上使いにくく，安定にするために 余計な計算量が掛かる．
まとめ
今回は，アルゴリズムの解析，ソートアルゴリズムと安定ソートを簡単に紹介しました．
実際にプログラムを書いていてデータ構造やアルゴリズムを変えるだけで，
計算量がO(n^2)からO(n)またはO(logn)になることがあります．
O(n^2)のアルゴリズムは実行にとても時間がかかるため，
O(logn)まで効率化できると実行時間がとても速くなり
アルゴリズム・データ構造の重要性がわかるかと思います．
この機会に遅いプログラムがあればプロファイリングを利用する等して，
原因となる部分を見つけデータ構造・アルゴリズムを見直してみて下さい．
BFSの実装を改善してO(n^2)からO(n)にした記事はこちらをご覧下さい．
Reference
