読者です 読者をやめる 読者になる 読者になる

計算量について

計算量とはなんぞや
プログラミングを初めて少しすると、そのプログラムは重いとか、何fpsでしか動かないとか、省メモリだとかいう言葉を耳にすることがあると思います。
これは結局プログラムを実行した際に必要な資源がどれくらいなのかということを言っています。
プログラムを実行する際に必要な資源とは、時間とメモリです。
この資源を「計算量」といい、時間とメモリそれぞれに「時間計算量」と「空間計算量」という計算量の評価尺度があります。

時間計算量
時間計算量は、先程も述べたようにプログラムを実行する際に必要な時間のことを示します。
しかし、これでは漠然としすぎていてよくわかりません。そこで、数学や物理を勉強したことある人はオーダーというものを見たことがあると思います。
記号でいうとOというものです。これはサイズnのデータが渡されたときにどの程度の計算量を必要とするかを示しています。
例としてはO(n^2)とかO(n \log n)という風に書きます。
詳しい定義については後日記述します。

空間計算量
空間計算量は、プログラムを実行する際に必要なメモリ量を示します。
こちらも時間計算量と同じようにオーダー記法を用いてよく示されます。

最近ビッグデータやIoTなどと騒がれていますが、このような膨大なデータを扱う際にはなるべく省資源で実行可能なプログラムが好まれます。
皆さんもぜひ計算量を意識したプログラムを書きましょう。