最近はアルゴリズムを勉強している。
なかなか頭に入ってこないので、アウトプットをして整理する。
なお、今回はO記法（オーダー記法）の話。
- O記法（オーダー記法）とは何か？ ⇒ 計算量を大雑把に評価したものを表現できる記法のこと。
どんな記法か？ ⇒ O(n)やO(n2)やO(log n)といった感じで表現する。
本当は3つだけはないのだが、私のような初心者はとりあえず3つ覚えておけば良いと思っている。
あとは、新しく出てきたときに随時覚える。
なお、計算量のO記法（オーダー記法）の考え方は、for文等の反復処理に要する計算時間を測定する。
// 計算量: O(n) for i := 1; i <= n; i++ { // なにかしらの処理 } // 計算量: O(n^2) for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { // なにかしらの処理 } } // 計算量: O(log n) func binary_search(key int) int { result := -1 left := 0 right := len(a) - 1 for right >= left { mid := left + (right-left)/2 if a[mid] == key { result = mid break } else if a[mid] > key { right = mid - 1 } else if a[mid] < key { left = mid + 1 } } return result }
O(n) について
n に比例した回数の反復処理に要する計算時間。
- n=2の場合: 2 ⇒ O(2) // 2回反復が必要
- n=3の場合: 3 ⇒ O(3) // 3回反復が必要
- n=4の場合: 4 ⇒ O(4) // 4回反復が必要
コードで表すと、以下のような for 文（反復処理）になる
for i := 1; i <= n; i++ { // なにかしらの処理 }
O(n2)について
n2 に比例した回数の反復処理に要する計算時間。
n2は 指数 。 指数 とは、「ある数・文字の右肩に記して、それを何度掛け合わせるかを示す数字・文字」のこと。
- n=2の場合: 22 = 4 // 4回反復が必要
- n=3の場合: 23 = 8 // 8回反復が必要
- n=4の場合: 24 = 16 // 16回反復が必要
指数が2なので、nが倍あるということ。O(n)と同じようにコードで表すと、以下のような for 文（反復処理）になる。
O(n2)はその倍。O(n3)はその倍の倍になる。
// 計算量: O(n^2) for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { // なにかしらの処理 } } // 計算量: O(n^3) for i := 1; i <= n; i++ { for j := 1; j <= n; j++ { for k:= 1; k <= n; k++ { // なにかしらの処理 } } }
O(lon n)について
log n に比例した回数の反復処理に要する計算時間。
log は、対数。対数とは指数の逆の概念。
指数は、「ある数・文字の右肩に記して、それを何度掛け合わせるかを示す数字・文字」を指した。
対数は、「指数の結果に対して、何度掛け合わせればその結果になるのか」を表す。
たとえば、23 = 8 で 「2を何度回掛け合わせるれば8となるか」を表す。答えは3になる。
ここで、実は対数は指数の数と同じになることに気づく。
「2を何度回掛け合わせるれば8となるか」は、逆に言えば「8を何回2で割れば1になるか」とも言える。
O(n2)のときと同じように考えてみる。（底は2と仮定する)
- n=2の場合: log2(2) = 1 // 1回反復が必要
- n=3の場合: log2(3) = 1.5 // 1.5回反復が必要
- n=4の場合: log2(4) = 2 // 2回反復が必要
- n=8の場合: log2(8) = 3 // 3回反復が必要
O(n)と比べると、反復回数がnに比例して半分になっていることがわかる。
以前書いた二分探索法を思い出す。二分探索法というのは、「真ん中で切手片方に絞っていく方法」。
つまり、反復回数がnに比例して半分する二分探索法のようなものは計算量がO(log n)ということになる。
以下、二分探索をコードで表すと以下のような for 文（反復処理）になる。
func binary_search(key int) int { result := -1 left := 0 right := len(a) - 1 for right >= left { mid := left + (right-left)/2 if a[mid] == key { result = mid break } else if a[mid] > key { right = mid - 1 } else if a[mid] < key { left = mid + 1 } } return result }
いきなり二分探索法のコードが出てくると混乱するが、単純にO(log n)をコードで表したいだけなら、以下のような for 文（反復処理）でも良い。
for i := 1; i <= n; i = i * 2 { // なにかしらの処理 }
O記法（オーダー記法）のO(n)やO(n2)やO(log n)を反復処理で書くと、どのような実装になるかがわかった。
O(log n) < O(n) < O(n2)の順番に早いのだということもわかった。
一般家庭にあるPCで1秒間で処理できる計算ステップ回数は109 = 1,000,000,000回 程度と言われてるらしい。
この3つに対して、nに応じた計算ステップ回数の変化を表で表現してみると、O(log n)のアルゴリズムが大変高速であることがわかる。
| n | log n | n2 |
|---|---|---|
| 5 | 2 | 25 |
| 100 | 7 | 10,000 |
| 1,000 | 10 | 1,000,000 |
| 10,000 | 13 | 1,000,000,000 |
| 100,000 | 17 | - |
| 1,000,000 | 20 | - |
| 10,000,000 | 23 | - |
| 100,000,000 | 27 | - |
| 1,000,000,000 | 30 | - |
ちなみに、O記法（オーダー記法）は定数倍の違いや低の違いはすべて無視する。
その理由は、O記法（オーダー記法）が、そもそも計算量を大雑把に評価したものである。というところあり、計算量というのは、コンピュータの環境やプログラミング言語、コンパイラによっても変わってくるので、アルゴリズムの計算時間を議論するときには定数倍や低次の項の影響を受けないようにするために、O記法（オーダー記法）は定数倍の違いや低の違いはすべて無視するようにしている。
ここまでが、アルゴリズムの概要。次はいよいよ設計技法。
