計算量

計算量とは 計算量とは、アルゴリズムを評価する指標で、どのくらい計算に時間がかかるかを表したものである. 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....