※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
＃02:計算量
このチャプターでは、計算量について学習します。
時間計算量: アルゴリズムを実行するのに必要な計算時間が、入力に対してどのくらいになるかを表す指標。
空間計算量: アルゴリズムを実行するのに必要なメモリ量が、入力に対してどのくらいになるかを表す指標。
単に計算量といった場合、時間計算量を指すことが多い。
入力サイズを表す変数を用いた関数として表現する。
厳密に計算量を見積もることは難しいため、大まかに表現する漸近的記法を用いる。
見た目では同じでも、実際の計算時間やメモリ量には大きな差が生まれることがあるため注意。
次の 2 つのポイントを押さえておく。
・係数は省略する
・支配的な項だけを残す
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) という大小関係がある。
また、日常的に使われるコンピュータでは、 1 秒間に 10^8 回程度の計算が可能。
入力の大きさの上限と計算量を考慮して、アルゴリズムを設計する。
最良計算量: 最も計算量が小さくなるような入力を与えたときの計算量。
最悪計算量: 最も計算量が大きくなるような入力を与えたときの計算量。
平均計算量: すべての入力に対する計算量を平均したもの。
理論的には最悪計算量が考慮されることが多いが、実用上では平均計算量を主に考慮することがある。
最良・最悪・平均計算量はそれぞれ異なる値になることがある。