この記事で解決できる問題
- プログラミングの世界における計算量オーダーを理解したい
- アルゴリズムごとの計算量が知りたい
- どの程度の計算量を目指せばよいか基準が欲しい
この記事ではプログラミングの世界によく出てくる、計算量（オーダー）について解説します。
学校の「データ構造とアルゴリズム」の授業などで習いますが、分からないまま通りすぎてしまった人も多いと思います。
この記事を読めば、学校の試験や実務のプログラミングで困らない程度の知識を得ることができますよ！
記事の前半では計算量オーダーとは何なのか？についての解説、後半ではアルゴリズムの一覧 や アルゴリズム選択の目安、基準について解説しています。
最後に、プロのエンジニアである私が実際にどのような場面で計算量を用いているのかについても言及しました。
皆さんが求める内容が含まれていると思いますので、ぜひ最後まで読んでみてくださいね！
目次
計算量について
計算量とは？
計算量とは、あるアルゴリズムを使った時の演算の性能を表す大雑把な指標 のことです。
計算量は大きく2つに分けられます。
計算量の種類
- 時間計算量（処理時間の計算量）
- 空間計算量（メモリ使用量の計算量）
単に計算量（オーダー）と呼ぶ場合、通常は時間計算量の方を指します。
プログラミングにおいて、処理時間の方が問題になることが多いからだと思います
英語では何という？
計算量は英語で、time complexity (時間計算量)、space complexity (空間計算量) と言います。
O記法（オーダー記法）とは？
特定のアルゴリズムでの演算が、どれくらい掛かるかを表した記号です。
処理対象のデータが非常に大きくなった時の処理時間を大雑把に表します。
処理対象のデータ数を N で表していて、よく使われるものは以下のものがあります。
O記法の種類
- O (1)
- O (log N)
- O (N)
- O (N log N)
- O(N2)
※上に行くほど処理が早い
ちょっと例を挙げてみましょうか
例えば処理すべきデータが100万件あるとして、
- O(1)のアルゴリズムなら数十ミリ秒
- O(log N)なら数百ミリ秒
- O(N)なら数秒
- O(N log N)なら数十秒
- O(N2)なら数分
ぐらい掛かるな、とざっくり見積もるために使います。
なので、実際に掛かる時間はあまり正確ではありません。
アルゴリズムによって文字通り桁が違うレベルで早くなる、という性能の基準を表すために用いられるものがO記法です。
アルゴリズムの一覧表
処理時間が短い順（性能が良い順）に代表的なオーダーをまとめます。
計算量の一覧
| O記法 | 概要 | 使用例 |
|---|---|---|
| O (1) | 定数時間 ・処理時間がデータ量に依存しない ・必ず一発で取得できる | ・配列要素へのアクセス ・ハッシュテーブルによるデータ検索 ・連結リストへの追加/削除 |
| O (log N) | 対数時間 ・処理をひとつ行うたびに処理対象を何割か減らせるようなアルゴリズム ・データ量が増えても計算時間がほとんど増えない ・多くの場合これ以上の改善は不要 | ・ソート済み配列の二分探索 |
| O (N) | 線形時間 ・データ量の分だけ時間が掛かる ・forループ１回分 ・N回もしくはNに比例する回数以内のループで処理が終わる場合 | ・非ソート配列の探索 |
| O (N log N) | 準線形、線形対数時間 ・ちょっと重いO(N)程度 ・マージソートのように二分木でデータを分割し、かつそれらをリニアサーチするようなアルゴリズムの計算量 ・二分木のオーダー(log N) × リニアサーチのオーダー(N) をかけあわせてN log Nになる | ・クイックソート ・マージソート ・ヒープソート |
| O (N2) | 二乗時間 ・要素からすべての組み合わせのペアについて調べるようなアルゴリズム ・工夫しないソート処理など ・二重のforループ ・これ以上は処理が遅すぎて使いにくい | ・挿入ソート ・バブルソート |
| O (N3) | 多項式時間 ・三重ループを伴う配列全体の走査 | ・行列計算 |
| O (kN) | 指数時間 ・要素を取り出すときのすべての組み合わせについて調べるようなアルゴリズム ・N軒の家をどの順序で回ったら最短距離になるか | ・ルービックキューブの総当たりによる解法 |
| O (N!) | 階乗時間 ・Nの階乗に比例した時間 | ・巡回セールスマン問題の総当たりによる解法 |
計算量の目安
計算量の目安としてとても分かりやすい表現があったので紹介します。
（多項式オーダーの世界）
O(1)，O(logn)，O(n)，O(nlogn)，O(n^2)，O(n^3)，O(n^100)
ーーーーー越えられない壁ーーーーー
O(2^n)，O(n!)
個人的には O(N log N)より遅ければ要改善かなと思います
まとめ
それでは、最後にここまでの内容をまとめます。
要点まとめ
- 計算量には、時間計算量と空間計算量の２つがある
- 単に計算量という場合は、時間計算量のことを指す
- O記法（オーダー記法）でざっくりとした処理時間を表す
- 同じことをする処理でも、計算量はアルゴリズムによって変わる
実際の業務では、このデータ量に対してこのアルゴリズムでは遅すぎて業務に耐えられない、などと判断するために使います。
そういった場合に、より性能の高いアルゴリズムを思いつければ良いのですが、仕様を変更するとこで対処することも多いです。
リレーショナルデータベースからインメモリデータベースに変えることなども選択肢になるかも知れません。
一つの問題に対して複数の解決策を思いつくようになれると良いですね。
それでは、また他の記事でお会いしましょう！
参考サイト
- 一週間で身につくアルゴリズムとデータ構造|応用編第1日目：アルゴリズムと計算量
- 時間計算量とは - IT用語辞典
- 空間計算量とは - IT用語辞典
- オーダー記法・その1：使用例からの導入 - あざらしとペンギンの問題
- 計算量を具体的に見てみる - きしだのはてな
- オーダー記法の定義と大雑把な意味 | 高校数学の美しい物語
- 時間計算量 - cppreference.com
- [初心者向け] プログラムの計算量を求める方法 - Qiita
- ランダウの記号 - Wikipedia
参考書籍
- ゲームプログラマになる前に覚えておきたい技術 (P.486) Amazonリンク
（注）この記事はQiitaに投稿した過去の記事を再構成したものです
