計算量の仕組み

計算量とは、入力サイズnが増えたときに処理回数がどれだけ増えるかを表す指標です。O(1)は入力サイズに関わらず一定、O(log n)はnを繰り返し半分にして1になるまでの回数だけ増え、O(n)は比例して増え、O(n²)は急激に増えます。同じ問題を解く場合でも、選ぶアルゴリズムによってこの増え方は変わります。