SortedContainersの計算量まとめ

Last updated at 2025-04-28Posted at 2025-04-28

はじめに

SortedContainersのデータ構造たちは内部に_loadという値を持っており、この値に計算量が依存します。この記事ではその値を$M$、要素数を$N$として話を進めます。
また、挿入する要素同士の比較は$O(1)$で可能なものとします。

常にソートされた配列です。
他言語ではmultisetと呼ばれるかもしれません。

重複しない版のSortedListです。
内部にpythonのsetを持っているため、ハッシュ化できないオブジェクトの挿入やハッシュの衝突回避目的には利用できません。

操作	平均計算量	$ M = \sqrt[3]{N}$の場合¹	最悪計算量
add(存在しない要素)	$O(\log(N) + M + \frac{N}{M^2} )$	$O(\sqrt[3]{N})$	$O(N)$⁴
add(存在する要素)	$O(1)$	$O(1)$	$O(N)$⁴
discard(存在しない要素)	$O(1)$	$O(1)$	$O(N)$⁴
discard(存在する要素)	$O(\log(N) + M + \frac{N}{M^2} )$	$O(\sqrt[3]{N})$	$O(N)$⁴
pop	$O(\log(N)) + M + \frac{N}{M^2} )$	$O(\sqrt[3]{N})$	$O(N)$⁴
getitem(一般)	$O(\log(\frac{N}{M}))$	$O(\log{N})$	$O(\frac{N}{M})$ ⁵
getitem(先頭、末尾のバケット)	$O(1)$	$O(1)$	$O(1)$
contains	$O(1)$	$O(1)$	$O(N)$⁴
bisect_left	$O(\log(N))$	$O(\log(N))$	$O(\log(N))$
bisect_right	$O(\log(N))$	$O(\log(N))$	$O(\log(N))$
count	$O(\log(N))$	$O(\log(N))$	$O(\log(N))$
index	$O(\log(N))$	$O(\log(N))$	$O(\log(N))$
remove	$O(\log(N) + M + \frac{N}{M^2} )$	$O(\sqrt[3]{N})$	$O(N)$⁴
del	$O(\log(N) + M + \frac{N}{M^2} )$	$O(\sqrt[3]{N})$	$O(N)$⁴
clear	$O(N)$	$O(N)$	$O(N)$
update$(4K \geq N)$	$O(K\log(K))$	$O(K\log(K))$	$O(KN)$⁴
update$(4K \lt N)$	$O(K(\log(N) + M + \frac{N}{M^2}) )$	$O(K\sqrt[3]{N})$	$O(KN)$⁴

_loadの値を実際に$ \sqrt[3]{N} $と設定するのが、実行時間的に最速とは限りません。 ↩ ↩²
実際には最悪で$O(\frac{N}{M})$かかりますが、addやpop時の計算量で償却可能。 ↩
実際には$O(N)$かかりますが、追加の際の計算量で償却可能。 ↩
pythonのsetについて、ハッシュの衝突時ｎ各操作の最悪計算量が$O(N)$となることが原因でこの計算量となっています。 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰
実際にはaddやpopなどの計算量で償却されるのでボトルネックにはならない。 ↩