はじめに
こんにちは。将棋と筋トレが好きな、学生エンジニアのゆうき(@engieerblog_Yu)です。
プログラミングを実務で使っていく、勉強していく中で計算量という言葉を聞いたことはありますでしょうか？
計算量については、良いアルゴリズムを作るために、絶対に知っておいた方がいい知識です。
今回は計算量と計算量を表現するオーダー記法について、紹介していこうとおもいます。
計算量とは？
計算量とは読んで字の如く、プログラムが何かしらの結果を出すために必要な計算の量です。
計算量には、時間計算量と空間計算量の二つがあります。
単に計算量という場合には、時間計算量のことを言っている場合がほとんどです。
今回は時間計算量について、考えていきたいとおもいます。
時間計算量について
時間計算量とは、「アルゴリズムを構成する命令の実行時間の総和」と定義されます。
アルゴリズムを構成する命令の実行時間の総和は、各命令の実行回数とそれぞれの命令の実行に要する時間を、掛けて合計すれば計算することができます。
例えば、最短経路を導き出すアルゴリズムがあり、そのコードの実行に2秒かかったとするならば、時間計算量は２秒と計算することができます。
しかし実行時間の見積もりはコンピュータのハードウェアやプログラミング言語の処理系に依存します。
普通のスペックのPCとスーパーコンピュータの計算速度はもちろんスーパーコンピューターの方が速いですし、PythonよりC言語の方が計算速度は速くなります。
そこで命令の実行時間を、各命令の実行回数に着目して、大体の速さを表現しようとしたものがオーダー記法です。
命令の実行時間の総和 = 各命令の実行回数 × 実行に要する時間
命令の実行回数に着目して、近似したものがオーダー記法
オーダー記法について
アルゴリズムの計算量評価では、大体の概算で十分なことが多いです。
そのため漸近的計算量と呼ばれる概念が用いられます。
漸近的計算量を計算するために、オーダー記法(ラウダウの記号とも呼ばれる)が使われます。
何のことかわからなくなってきたと思うので具体例を挙げています。
アルゴリズムの中にn回繰り返すforループが二つあったとします。
一回あたりのforループの時間を\(T_1\)と表して、forループ以外の処理にかかる時間を\(T_2\)と表します。
すると計算量は\(nT_1+T_2\)と表すことができます。
この計算量を漸近的に考えていきましょう。
漸近的とはnを極端に大きくするということなので、nを100億くらいに大きいものだとイメージして考えてみましょう。
nが十分に大きいものである時、\(nT_1\)は\(T_2\)に対して極めて大きくなっていることがわかります。
つまり近似して\(T_2\)を省略することができます。
また\(T_1\)もハードウェアや言語の処理系に依存し、アルゴリズムの良し悪しにはあまり影響がありません。
つまり今回のアルゴリズムの計算量で漸近的に考えた場合、本質的に大切なのは、nとなってきます。
これをO(n)と表します。
T1n+T2をオーダー記法で表すとO(n)
計算量の比較
最後にオーダー記法で表した時の、大小比較についてです。
O(1) < O(logn) < O(√n) < O(n) O(nlogn) < O(n^2) < O(n^3) < O(k^n) < O(n!)
nを極めて大きくしたときに、どうなっているかを考えるのがコツです。
終わりに
今回はアルゴリズムの良し悪しを評価する指標として使われる、オーダー記法について紹介しました。
良いアルゴリズムを評価するために使われる指標として、扱いやすいものだと思うのでぜひ知っておきたい知識です。
本日はここまでです！
次回の記事でお会いしましょう！
他にもいろんな記事があるにゃ。
コメント