TL;DR
アルゴリズムの実行に必要な計算資源の量。入力データの長さを増やしたときに、実行時間や必要な記憶容量がどう増えるかを表す。
なぜ必要か
アルゴリズムが入力データの増大にうまく対応できるかどうかで、そのアルゴリズムが現実の問題を解くのに役立つかが決まる。計算量を見ると、入力が大きくなったときのアルゴリズムのスケーラビリティを比べられる。
仕組み
計算量には、時間計算量と空間計算量がある。時間計算量は、問題を解くのに必要なステップ数を、入力データの長さの関数として表したものである。空間計算量は、アルゴリズムが必要とする記憶容量を同じように表したものである。
計算量は、漸近的な振る舞いだけに注目し、定数倍を無視する ビッグオー記法で書くことが多い。計算モデルが違っても時間計算量は漸近的には定数倍しか変わらないので、この書き方なら計算モデルに依存せずに表せる。