アルゴリズム 基礎
まじめにアルゴリズムを勉強したこと無かったので、ちゃんと説明できるくらいまで勉強しようと思った!!
というわけで、忘れないようにメモ〜
アルゴリズム
「有限個の規則」と「有限回適用」がキーワード。
アルゴリズムを構成する規則の個数(有限個の規則)と、それを適用した時の処理の回数(有限回適用)が有限であることが,アルゴリズムの条件になる。
上記の数のによりアルゴリズムの性能が決定される。
評価
適用回数*1が少ない方が良いアルゴリズム。
計算量は入力サイズ*2「n」の関数である。関数名をFとすると、
- 線形探索の計算量は「F(n)=n」
- 2分探索は「F(n)=log2n」
と表すことができる。
計算量
アルゴリズムの性能を評価する際には計算量という尺度を用いられる。
メモリー容量(領域計算量)+ 時間(時間計算量) = 計算量
通常は,メモリー消費量よりも実行時間を重視することが多いので,計算量と言えば時間計算量を指すのが一般的だそうな。
また、計算量を求める際には、通常「最大計算量」*3が使われるが、アルゴリズムによっては「平均計算量」*4についても考察しなければならない物もある。(クイックソート等)
オーダ表現(O記法)
(10n^5 + 2n^3 + 9999) という計算量結果があるとして、この場合漸近的計算量で表すと「n5」となり、O記法では「O (n^5)」 と表せる。
オーダ表現ルールとは、
- 次数の小さい項は無視。
- 定数の小さい項も無視。
というもので、F(n)の中から最も増加率の大きいものを抽出します。
(上の例では2n^3 と 9999 が省略される)
計算量の大小関係は次のようになる。
O(log2n)<O(n)<O(n・log2n)<O(nC)<O(Cn)<O(n!) ←はやい おそい→ [n:入力サイズ、C:定数]
O(n)やO(n2)などの多項式時間アルゴリズムに比べて,O(2n)やO(n!)などの指数関数時間アルゴリズムは一気に膨れ上がる。よって,指数関数時間アルゴリズムは現実的ではない