C++における時間計算量

標準ライブラリのコンテナとアルゴリズムの時間計算量について解説する。本記事で“計算量”と記述した場合、特に注釈のない限りは時間計算量を指す。

基本的な計算量と、C++における代表例

ここで説明する内容は一般論なので、特殊な条件は考慮しない。

• 要素数に依存しない初期化： $O(1)$
• 要素数に依存した初期化: $O(n)$
• ソートを伴う初期化: $O(n \log n)$

計算量（少ない順）	名称	C++における代表例
$O(1)$	定数時間 (constant)	デフォルトコンストラクタ デフォルトデストラクタ デストラクタ（子要素が無いもの） ムーブコンストラクタ swap 操作 生配列の添え字アクセス （時に規定がない場合の計算量とメモリ使用量として想定できるもの）
（記号は特に無し）	償却定数時間 (amortized constant)	std::vector::push_back （たまに非常に長い時間がかかるが通常は短い時間で完了するために、平均的には定数時間と同等まで償却できるもの）
$O(\log n)$	対数時間 (logarithmic)	距離や範囲の再計算 （前方向イテレータ要件を満たさないイテレータ範囲による初期化におけるメモリ再確保）
$O(n)$	線形時間 (linear)	デストラクタ（全ての要素を破棄する必要があるもの） コピーコンストラクタ std::unordered_set 同士の等値比較 （平均計算時間）
$O(n \log n)$	線形対数時間 (log-linear)	std::sort 一般的に 速い とされるソート （平均計算時間）
$O({n^2})$	二乗時間 (quadratic)	二重ループ 一般的に 遅い とされるソート （最悪計算時間） std::unordered_set 同士の等値比較 （最悪計算時間）
$O({n^c}), \exists c\ge 1$	多項式時間 (polynomial)	多重ループ 行列計算
$O({c^n}), \exists c\ge 1$	指数時間 (exponential)	ナイーブな素数探索と因数分解 （遅すぎるため実用的でない）
$O(n!)$	階乗時間 (factorial)	ナイーブな行列計算、巡回セールスマン問題の総当たり計算 （遅すぎるため実用的でない）

コンテナの計算量

本項ではセマンティクス全体の計算量を記載する。ただし内部実装による複数回の計算が明らかでかつ直感と反する場合は、これを併記する。

ここでは、以下に示すような通常の条件下での計算量を記載する。

• 処理系定義の最適化を考慮しない
• メモリ再確保が起こらない
• 要素自体はムーブ構築される

限定された条件下における厳密な計算量については、各メンバ関数のリファレンスを参照すること。

通常のセマンティクスと計算量

種類	N要素の初期化	コピー	先頭	絶対位置	末尾	位置挿入	位置削除
セマンティクス	C c{first, last};	C c2{c1}; auto c2 = c1;	e = c.front();	e = c[i]; e = c.at(i);	e = c.back();	c.insert(pos, e);	c.erase(pos);
生配列 array	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(1)$	-	-
vector	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$ （※数と位置に応じて）	$O(n)$ (※破棄 $n$)
deque	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(1)$	$O(n)$ （※構築 $n$ + 伸長 $n$）	$O(n)$ （※破棄 $n$ + 収縮 $n$）
list	$O(n)$	$O(n)$	$O(1)$	-	$O(1)$	$O(1)$	$O(1)$ (※破棄 $n$）
forward_list	$O(n)$	$O(n)$	$O(1)$	-	-	$O(1)$	$O(1)$ (※破棄 $n$）
set	ソート済： $O(n)$ 未ソート： $O(n \log n)$	$O(n)$	-	-	-	ヒント付	ヒント付
unordered_set	平均： $O(n)$ 最悪： $O(n^2)$	平均： $O(n)$ 最悪： $O(n^2)$	-	-	-	ヒント付	ヒント付
map	ソート済： $O(n)$ 未ソート： $O(n \log n)$	$O(n)$	-	$O(\log n)$	-	ヒント付	ヒント付
unordered_map	平均： $O(n)$ 最悪： $O(n^2)$	平均： $O(n)$ 最悪： $O(n^2)$	-	平均: $O(1)$ 最悪: $O(n)$	-	ヒント付	ヒント付

特別なセマンティクスと計算量

種類	検索	一致範囲	指定挿入	指定削除
セマンティクス	it = c.find(k);	b = c.equal_range(k);	c.insert(e); c.insert({k, v});	c.erase(k);
連想コンテナ	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n), n = size()$
ハッシュセット	平均： $O(1)$ 最悪： $O(n)$	平均： $O(n), n = count(k)$ 最悪： $O(n), n = size()$	平均： $O(1)$ 最悪： $O(n)$	平均： $O(n), n = count(k)$ 最悪： $O(n), n = size()$
ハッシュマップ	（同上）	平均： $O(1)$ 最悪： $O(n)$	（同上）	（同上）
その他のコンテナ	-	-	-	-

凡例

• C
  コンテナのクラス
• c, c1, c2
C クラスのオブジェクト
• e
  要素（通常は C::value_type）
• first, last
InputIterator コンセプトを満たす [first, last) 範囲のイテレータ
• it
  検索結果の要素の位置を示すイテレータ（通常は C::const_iterator）
• b
  下境界と上境界のペア（通常は std::pair<C::const_iterator, C::const_iterator>）
• pos
  挿入位置を示すイテレータ（通常は C::const_iterator）
• k
  連想コンテナにおけるキー（通常は C::key_type const& ）
• i
  添え字（通常は std::size_t）
• $count(k)$
  操作の対象となった要素数
• $size()$
  コンテナの全要素数
• 連想コンテナ
  C++に古くからあるコンテナ。
  重複要素を許容するものと許容しないものがあり、格納順が規定されている。
  set 、 multiset 、 map 、 multimap
• ハッシュコンテナ、ハッシュセット、ハッシュマップ
  C++11から入った、内部実装にハッシュテーブルを用いるコンテナ。
  重複要素は許容されず、格納順も規定されない。
  unordered_set 、 unordered_map
• 「-」 （半角ハイフン）
  そのセマンティクスが対象のコンテナに存在しないことを示す。
• 「ヒント付」
  限定された条件下の操作でヒントを正しく指定すると、計算量は大幅に減る。
  詳細については、各メンバ関数のリファレンスを参照すること。

備考

• $O(size())$ と $O(N)$ はどちらも $O(n)$ である。ここで、 $size()$ はコンテナ自身の要素数、 $N$ は操作の対象となった要素数。
• あるセマンティクスの全体の計算量が 線形時間 でも、内部実装では 線形時間未満の複数の操作 が行われることがある。
• 操作対象の要素数 $N$ より全要素数 $size()$ の方が、結果的にプログラムの実行時間に与える影響が大きいことがある。
• 先頭または末尾への１要素の挿入／削除が特別にサポートされているコンテナでは、その操作の計算量は基本的に 定数時間 である。
  （例： std::deque::push_front 、 std::deque::pop_back ）
• 前項の例外として、 std::vector::push_back の計算量は、 定数時間ではなく 、 償却定数時間 である。
• std::array 以外のコンテナにおける swap 操作の計算量は、 定数時間 である。
• std::stack 、 std::queue 、 std::priority_queue 等のコンテナアダプタの計算量は、内部実装の計算量に準じる。
• 重複要素を許容する連想コンテナの計算量は、重複要素を許容しない連想コンテナの計算量に準じる。
• std::forward_list はゼロオーバーヘッドを重視した設計のため、コンテナの要素数を 定数時間 で取得することはできない（他のコンテナは通常は定数時間として規格に規定されている）。
• std::valarray は専ら数値演算を目的として処理系定義の最適化が行われる可能性が高く、厳密な計算量の定義が難しいため、本記事では解説しない。

参考：セマンティクスについて

この記事では、C++が標準規格でサポートしている セマンティクス における計算量を解説した。

セマンティクスとは、プログラムの 意味 を指す用語である。対応する概念として、「シンタックス （構文） 」がある。ある操作がC++標準規格上の関数として用意されているとき、シンタックスと同時にそのセマンティクスがサポートされているといえる。

重要なことだが、 複数のシンタックスの組み合わせを使って問題を解決することができても、そのプログラミング言語でそのセマンティクスがサポートされていない場合はしばしば非効率になる。 ましてやC++はローレイヤーな書き方も可能な言語なので、やろうと思えば何でも出来てしまう。しかし、そのようなローレイヤーな構文の組み合わせで問題を解決することができても、効率的なプログラムにはならない。

効率的な書き方が出来ない場合は、そのプログラムが対象とする問題が計算複雑性理論上既知な難題として知られているはずである（※P≠NP予想などによる）。効率的に解決できないとして知られている有名な問題には、素数判定や巡回セールスマン問題などがある。これらの厳密解は 多項式時間 以下で解くことができないが、近似解で妥協することや問題設定を見直して簡単にすることで多項式時間で解く現実的な手法が色々な人によって研究されている（詳細は割愛）。

C++が言語としてサポートしていない操作を行おうとしたとき非効率になる例として、 「コンテナの絶対位置の要素を取得するプログラム」 を書く例を以下に示す：

std::vector の場合

この操作は std::vector では生配列と同じように、 定数時間 で終わることが規定されている。

std::vector<int> v;
auto const e = v[42]; // 42番目の絶対位置の要素を取得

std::advance() を使って同じく 定数時間 で書くこともできる。

std::vector<int> v;
auto it = v.cbegin();
std::advance(it, 42); // `v[42]` と同等になることが規格で保証されているので、定数時間になる
auto const e = *it;

全く同じことを for ループで書くこともできる：
（※このコードは悪い書き方の例なので、このような書き方をしてはいけない。これは 定数時間にはならない）

auto it = v.cbegin();
for (int i = 0; i < 42; ++i) {
  ++it;
}

auto const e = *it;

std::list の場合

std::list では v[i] のセマンティクスはサポートされていない（連結リストなので当然である）。そのかわり、 std::advance() を使って先頭から i まで辿ることで同じプログラムを書ける。

std::list<int> l;
auto it = l.cbegin();
std::advance(it, 42); // 42回インクリメントするのと同じ。定数時間にはならない！
auto const e = *it;

これはvectorの例のように for 文で書くのと同じである。これはサポートされていないので、非効率になる。