計算量の話 - Emileの備忘録

この記事は学ロボAdvent Calendar 2022の1日目の記事です。
魁はアドカレ作成者の私が務めさせて頂きます。

adventar.org

この記事ではプログラムの計算量などについて軽く軽く軽くおさらいします。

==============目次==============

0. はじめに
1.計算量とは?
2.漸近記法
3.具体例
- ・3.1 クイックソート
- ・3.2 マージソート
4.終わりに
5.出典

===============================

0. はじめに

プログラムを書いた事がある人であれば、「計算量」や「漸近記法」の概念に一度は触れた事があると思います。

これらの概念はアルゴリズムを評価する際には欠かせない物であり、
ロボットなど、省メモリ/リアルタイム性が問われるソフトウェアの開発場面では、
常に計算量を意識してコーディングしているのでは無いでしょうか？

ですが、例えば $O(n)$ の定義は?と聞かれると意外と怪しかったりするかもしれません。
この記事では、そういった基本的な概念のおさらいをしていく事を目指します。

ふと忘れてしまった時に思い出すキッカケに出来るような記事として使っていただければ幸いです。

1.計算量とは?

計算量というのは、雑に言うとアルゴリズムを実行する時に要する計算資源の事です。

計算量と呼ばれる物には以下の2種類があります。
・時間計算量 : アルゴリズムを実行するのに要するステップ数 (どのくらい手間がかかるか)
・空間計算量 : アルゴリズムを実行するのに要する記憶領域の量 (どのくらいメモリなどを食うか)

例えば時間計算量だったら、
問題のパラメータに依存しない最小限の処理を1ステップとして考えると分かり良いと思います。
「for文で1,2,...,nを足し合わせるのはnステップかかる」的な感じです。

勿論、問題のインスタンス毎に"具体的な"ステップ数や記憶量は変化するので、
「だいたいこれくらい」というのを表現するのに後述の漸近記法を用います。

2.漸近記法

まずはよく使われる記法の定義を記述します。

・ $\Theta ( g(n) ) = \{ f(n) : 正の定数c_1,c_2,n_0が存在して\ \ 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)\ \ (\forall n \geq n_0)\ \ が成立 \}$

$f(n) \in \Theta(g(n))$ の時は、 $f(n)$ は $g(n)$ の定数倍の範囲に限定されます。

ちなみに $\Theta$ は $\theta$ の大文字です。

・ $O(g(n)) = \{f(n) : 正の定数c,n_0が存在して\ \ 0 \leq f(n) \leq c g(n)\ \ (\forall n \geq n_0)\ \ が成立 \}$

$\Theta(g(n))$ は $g(n)$ による(定数倍の範囲の)漸近的上界を与えます。
勿論 $\Theta(g(n)) \subset O(g(n))$ が成立します。 $O(n) \subset O(n^2)$ とかも成立するので雑に乱用できます。

・ $\Omega(g(n)) = \{f(n) : 正の定数c,n_0が存在して\ \ 0 \leq c g(n) \leq f(n)\ \ (\forall n \geq n_0)\ \ が成立\}$

$\Omega(g(n))$ は $g(n)$ による(定数倍の範囲の)漸近的下界を与えます。

※ 必要性に応じて、これらを使い分けるという話です。基本的に $O$ 記法を用いるのが丸い様に感じます。
※ 実際、多くの本では $O$ 記法を用いて計算量を評価している気がします。(個人の感想です。)

これらの記法は乱用すると非常に便利ですが、誤用すると怒られが発生するので注意しましょう。
他にも $o(g(n))$ とか色々あるのですが、この記事ではここまでにしておきます。

3.具体例

ここからは幾つかのアルゴリズムを例に上げて計算量を考えていきます。
殆どの場合 $\Theta$ は $O$ として問題無いとは思いますが、今回は書き分けています。
(そこの精度が要求される場面は稀だと思います。)

・3.1 クイックソート

クイックソートは非常に効率の良いソートアルゴリズムとして知られています。
GCCのsortではクイックソートの最悪ケースを改善したイントロソートが用いられています。

分割統治アルゴリズムの一種で、配列の右端をpivotとして選択し、
配列をpivotより大きい要素のみの部分列と小さい要素のみの部分列に入れ替え・分割する操作を
各部分列に繰り返し適用する事で、ソートを行うアルゴリズムです。

後述するマージソートと違って、均等に分割できるかで計算量が変化します。
最悪の場合は、分割時に長さ $n$ の配列を長さ $n-1$ の配列と長さ $1$ の配列に分割した場合に対応します。
最良の場合は、均等に分割する場合に対応します。(後述のマージソートと同じ考え方で求められます。)

以上をまとめると、クイックソートの時間計算量は
・最悪計算量 : $\Theta(n^2)$
・最良計算量 : $\Theta(n\log n)$
・平均計算量 : $O(n \log n)$
となります。(詳細な計算は他の記事や本に任せます。)

直感的には最悪の場合は分割に $\Theta(n)$ 掛かるので、 $T(n) = T(n-1) + \Theta(n)$ を解く事で、
$\Theta(n^2)$ の時間計算量がかかる事が分かります。

・3.2 マージソート

マージソートも分割統治アルゴリズムの一種であり、詳細は省きますが、
配列を中央で2つの部分列に分割し、それぞれの部分列にソートを適用した物をマージする構造になっています。
一番好きなソートアルゴリズムです。

個人的にはクイックソートよりも直感的に何をやっているのかが把握しやすいと思います。
(実際は両方とも分割統治法に分類されるアルゴリズムで、全く同じ構造に従っています。)

分割操作は定数時間、マージ操作は配列の長さ $n$ に対して $\Theta(n)$ で計算できるので、
このアルゴリズムの時間計算量は、元の配列の長さを $n \in \mathbb{N}$ として、以下の様になります。
・最悪計算量 : $O(n \log n)$
・最良計算量 : $\Omega(n \log n)$
・平均計算量 : $\Theta(n \log n)$