計算量とは

計算量とは、アルゴリズムの実行に必要な時間（時間計算量）や記憶容量（領域計算量）を、入力データの大きさnの関数として表した尺度である。

データが大きくなったときの増え方に注目し、O記法で表す。例えば線形探索はO(n)、二分探索はO(log n)、バブルソートはO(n²)、マージソートはO(n log n)である。nが大きくなるほど、計算量の違いが処理時間に大きく表れる。