計算量とは

計算量とは、アルゴリズムを評価する指標で、どのくらい計算に時間がかかるかを表したものである.
O(n) のように表記する.
O は order からきており, O(n) は おーだーn のように読む.
プログラマがプログラムを書く理由は, 問題を 早く , 楽に 解くためである.
せっかく作ったプログラムが非現実的な時間かかってしまっては意味がない.
なのでプログラムを書くときは常に頭の中に計算量を意識しておく必要がある.

計算量の概念について

すごく雑に解釈するとループの回数に一致する.
次のようなプログラムがあったとしよう.

for i := 0; i < n; i ++ {
    fmt.Println("にゃーん")
}

このプログラムの計算量は O(n) です.
n が増加すると計算時間は線形に増加する.

次のようなプログラムはどうであろうか?

for i := 0; i < n; i ++ {
    for j := 0; j < n; j ++ {
        fmt.Println("にゃーん")
    }
}

このプログラムの計算量は O(n^2) になる.
次のような場合はどうなるか？

for i := 0; i < n; i ++ {
    fmt.Println("にゃーん")
}

for i := 0; i < n; i ++ {
    for j := 0; j < n; j ++ {
        fmt.Println("にゃーん")
    }
}

この場合 O(n^2 + n) の用になりそうである.
しかし, 計算量を考えるときは O(n^2) であるものとして扱う.
理由は計算量を考慮しないといけない場合というのは処理時間が長くなる場合である.
処理時間が長くなるというときというのは n が十分に大きいときである.
n が十分に大きいとき O(n^2+n) の計算時間は O(n^2) のときのものに近似できる.
なので複数の項を持つ計算量の場合は今回のように最大の項を持つものを計算量として扱う.

あまりピンと来ない人は実際にグラフを書いて見るとよい.