計算量オーダーと計算時間の関係性 ～オーダー記法の注意点～

実計算時間をオーダー記法(ランダウ記号)で見積もる上での問題点

1.記事の概要・対象読者

計算時間の比較には$O(n\log{n})$のようなオーダー記法がよく使われますが、実際にはオーダー記法から予想される計算時間と計測結果が大きくずれていることがよくあります。そこで本記事ではそのようなズレが起きている具体例を挙げることで、そういったずれが起きた際の理解の助けとなることを目的としています。

読者としては計算量のオーダー記法が何を表しているかは理解していて、かつプログラムの計算時間に関心のある方を対象としてしています。

2.定義・前提知識

今後の議論でオーダー記法を多用するため、その定義を簡単にまとめておきます。

通常オーダー記法とは数学のランダウ記号を使う計算量の表記法を指し、計算量が$O(g(n))$であるとは

$$\lim_{n \rightarrow \infty} \frac{\rm{(計算量)}}{g(n)} = c \tag{1}$$

を満たす定数$c$が存在するという意味です。例えばある計算Aの計算量が$(3n^2+11n+6)$である場合には、$g(n)=n^2,c=3$で上式が成立するので、Aの計算量は$O(n^2)$と表記されます。

ただし$g(n)=n^3,c=0$でも上式は成立して「Aの計算量は$O(n^3)$」も正しくなってしまいます。そこで計算科学では通常$c \neq 0$が条件として入り、本記事でもこれを条件に含めた狭義の定義を採用します。

3.オーダー記法の基本的な使い方

与えられたデータの大きさ$n$に依存して計算量が変わる2つのアルゴリズムA,Bに対して、「どちらの方が速いか？」を調べるには通常オーダー記法で比較されます。例えば挿入ソートとクイックソートのどちらの方が速いか比べる場合、前者の計算量は$O(n^2)$、後者は$O(n\log{n})$となるので、より計算量の少ないクイックソートの方が速いアルゴリズムである、と言われるわけです。

他にもオーダー記法はあるアルゴリズムの計算時間を見積もる際にも利用されます。例えば$n=10000$で挿入ソートに3秒かかった場合、$n=50000$の場合には$3秒 \times \left( \frac{50000}{10000} \right)^2 =75$秒かかるだろうと見積もれます。つまり時間のかかる非常に大きいサイズの計算の計算時間を、小さいサイズの計算の計算時間から推定できるわけです。これはプログラムの実行所要時間を測定する上で非常に有用な考え方です。

4.オーダー記法の限界

オーダー記法は上のように計算時間の比較や推定に使えるわけですが、実際にはこのようにして推定した計算量が実測値と合わないことが頻発します。ここではそのずれが起きる原因と、ずれが起きる例を挙げて見ていきます。

4.1 係数の影響

オーダー記法で計算量を表現する際、(1)の$c$の大きさに関する情報は消滅してしまいます。この$c$の大きさは動作環境や実装に大きく依存し、一概には評価できないのですが、実用上の速度差はこの係数で大きく変わります。 この影響を顕著に受ける例を挙げると次の表のようになります。

アルゴリズム	A	B
計算量(計算時間)/秒	$8n^2$	$n^2 \log{(1+n)}$
計算オーダー	$\bm{O(n^2)}$	$O(n^2 \log{n})$
$n = 1$	8秒	0.69秒
$n = 10$	13分	4.0分
$n = 100$	22時間	13時間
$n = 1000$	93日	80日
$\bm{n = 2980}$	2.3年	2.3年
$n = 10000$	25年	29年

これを見ると、オーダー記法上では$O(n^2)$であるAの方が速いと評価されますが、計算時間が2.3年以下の範囲ではBの方が速いです。実際には何年もかけて計算するのは現実的ではないので、
オーダー記法ではAの方が速いアルゴリズムですが、実用上速いアルゴリズムはBとなります。

特に素直な実装よりも速いとされるアルゴリズムは係数$c$が比較的大きくなる傾向があるので、係数の影響で速度が逆転する現象はよく見られます。

あなたが計算速度を評価する立場ならば、この係数も計測することでその影響を正しく評価できます。 実際に測定を行えば係数を求めることは比較的容易なので、それを用いてどの位の$n$で逆転するのか、それを実際の大きさと比較することで、現実に即した計算速度評価を行えます。

しかしハードウェアの進化に伴い実運用で扱う$n$が大きくなったり、異なる環境で実行したときに係数$c$が変化して速度が逆転する$n$が変わったりするため、環境に合わせて速度評価は変わります。

あなたがプログラムを高速化する立場ならば、定数倍の高速化を重視することが係数が大きい場合の対処法です。 オーダーが変化するような高速化には大規模なアルゴリズム変更が必要なことが多いですが、係数を変えるような定数倍の高速化なら小規模な改修で済むことが多いです。他には分割統治法を用いたアルゴリズムなら、$n$が大きいときにはAのようなアルゴリズムを、$n$が一定値以下まで分割されればBのようなアルゴリズムを使用するように切り替えることで、高速化が見込めます。

現実的には一定の範囲内の$\bm{n}$しか扱わない以上、定数倍の高速化の方がオーダーレベルの改善よりも高速化に寄与することもあります。

4.2 低次の計算量の影響

計算量オーダーで評価できるのはあくまで最高次のみです。もしそれ以外の項の寄与が大きければ、計算量全体に与える影響も無視できなくなります。

アルゴリズム	C	D
計算量(計算時間)/秒	$n^2 + 500n\log{(1+n)}$	$2n^2$
計算オーダー	$O(n^2)$	$O(n^2)$
最高次の係数$c$	1	2
$n = 10$	3.4時間	3.3分
$n = 100$	2.8日	5.5時間
$n = 1000$	52日	23日
$\bm{n = 4168}$	1.1年	1.1年
$n = 10000$	4.6年	6.3年

これを見ると、計算量オーダーは$O(n^2)$で両者同じ、その係数$c$はAの方が小さいので通常Aの方が速いと評価されますが、計算時間が1年以内ならBの方が速いです。つまり実用上はBの方が速くなります。

さらに計算時間の逆転が起きない範囲であっても、低次の計算量を無視できるわけではありません。 実際Cの方が速い$n=10000$において、低次の項は計算時間に対し32%もの寄与があります。

あなたが計算速度を評価する立場ならば、計算量オーダーの理論値と実測値を比較し、同じ挙動を示しているのかを確認するべきです 低次の項の寄与が大きい場合、計算量オーダーの挙動はそちらに引っ張られるはずです。すると理論値と実測値に挙動のずれが生じ、低次の項の効果が無視できないことが示唆されます。それをもとに計算速度の式を修正し、速度評価をより正確にできます。

あなたがプログラムを高速化する立場ならば、高速化するべきコードをきちんと特定するべきです。 低次の寄与が大きい場合、通常ボトルネックになる計算の核部分ではなく、前後処理や補助処理に時間がかかっている可能性があります。それぞれにかかっている時間を詳しく測り、原因を調べなければ、せっかく各部分を改良したのに効果が薄いとなりかねません。

4.3 並列化の影響

並列化可能率の違いにより、計算量オーダーが大きくとも計算時間が小さくなることがあります。

計算がアムダールの法則にしたがうとし、並列化できる割合を$P$、コア数をN、今回取り扱う問題の大きさを$n=1000$とするとき、並列化の影響を受ける例としては以下のようなものがあります。

アルゴリズム	E	F
計算量(計算時間)/秒	$n^2$	$n^2 \log{n}$
計算オーダー	$\bm{O(n^2)}$	$O(n^2\log{n})$
並列化可能割合$P$	0.3	0.95
$N=1$	12日	80日
$N=2$	9.8日	42日
$N=4$	9.0日	23日
$N=8$	8.5日	13日
$N=16$	8.3日	8.7日
$N=32$	8.2日	6.4日
$N=64$	8.2日	5.2日
$N=128$	8.1日	4.6日

これをみると、計算量としては$n^2$であるEの方が速いですが、並列数$N$が十分大きくなるとFの方が速くなります。つまり十分な計算資源があるなら、計算量が増えても並列化しやすいアルゴリズムの方が速くなりえます。

あなたが計算速度を評価する立場ならば、計算に使用するコア数を変えることで並列化の影響を評価できます。 今回のようにアムダールの法則に従うのであれば、これにより$P$を求め、それぞれの環境での計算速度を評価できます。

実際には並列化の影響はもっと複雑な挙動を示すので、パラメータを増やして近似する必要があります。

あなたがプログラムを高速化する立場ならば、実行するハードを考慮して高速化を行うべきです。 あなたが想定すべき実行環境が家庭用のノートPCなのか、それともスパコンなのかでE,Fいずれを採用するべきかは変わりますし、そんな極端な例でなくともCPUで実行するなら計算量の少ないEを、GPUで実行するなら並列化しやすいFを使うというような使い分けだってありえます。

すなわち計算時間を短くするため、ハードの特徴に合わせ計算量の多いアルゴリズムを採用することも検討するべきです。

4.4 メモリの影響

通常計算速度の指標として用いるのは「計算量」オーダーです。しかし実際のプログラムでは「計算」だけではなく「読み書き」も大量に行っており、後者の影響が顕著に表れる場合もあります。

アルゴリズム	G	H
計算量(計算時間)/秒	$n$	$n \log{n}$
メモリアクセス量/秒	$0.01n^2$	$n$
計算オーダー	$\bm{O(n)}$	$O(n\log{n})$
$n = 10$	11秒	33秒
$n = 100$	3.3分	9.3分
$\bm{n = 646}$	80分	80分
$n = 1000$	3.1時間	2.2時間
$n = 10000$	11.7日	1.2日

これをみると計算量ではGの方が小さいですが、$n$が十分大きくなるとメモリアクセスがボトルネックになってHの方が速くなります。

今回は極端な例を用意しましたが、実際の環境においてもキャッシュミスによって大きな$n$におけるメモリアクセス時間が大幅に増え、計算時間全体の律速になることは多いです。 この現象は計算量オーダーだけでは全く評価できません。

あなたが計算速度を評価する立場ならば、メモリアクセスが処理時間に大きく影響しうることを頭に入れておかなければなりません。 特にキャッシュミスに伴うアクセス時間の増加は$n$が一定値以上になると急激に現れることが多いので、小さい$n$での計測だけでは見落とされる場合も多いです。

あなたがプログラムを高速化する立場ならば、使っているメモリ量を意識して高速化を行うべきです。 キャッシュミスは当然キャッシュ量付近から起き始めるので、L1～L3キャッシュの量である1コア当たり数百KB～数MB付近からメモリアクセスの影響が出始めます。これを頭に入れておけば、$n$の増加に伴い計算時間が急に増加した場合でも、原因を特定しやすくなります。

5.そもそも計算時間を調べるのにオーダー記法は向いてない

ここまで計算量オーダーだけでは計算量や計算時間を正しく評価できない例を挙げてきましたが、元も子もないことを言えばオーダー記法は計算時間を単独で評価するのに適切な評価軸ではありません。

「2.定義・前提知識」で述べたように、もともとランダウ記号は数学で用いられてきた記号であり、変数$n$が十分大きい場合や小さい場合の議論を簡略化するために使われる記号です。つまり数学的に$n$は細かいことを無視できるほど極端な値をいれることが前提となります。

しかし$n$に依存する計算時間$f(n)$は現実的に可能な範囲に収まっていなければ、実際の計算を行えません。すなわちランダウ記号$\bm{O(g(n))}$はできるだけ大きな$\bm{n}$を要求している一方で、計算時間$\bm{f(n)}$は現実的に計算できるような$\bm{n}$であることを求めており、両者が$\bm{n}$に求める大きさにずれがあります。

ゆえにオーダー記法が計算量の評価として適切であるのはあくまで両者を満足するような範囲の$n$においてのみであり、それを超える範囲では今回上げたような問題点が現れてきます。

ただオーダー記法自体は理論の面では適切な評価方法であり、動作環境に左右されない評価方法であることが強みです。 上で挙げたものはいずれも演算能力の限界や、ハードウェアに依存して現れる現象なので、長期的な運用や様々な動作環境を見据えるのなら、信頼性の高い評価方法であることに間違いはありません。

6.まとめ

以上のことから、実計算時間を評価する際に、オーダー記法のみでは十分な評価方法とは呼べません。現実では係数や低次の項の影響が無視できない場合が多く、オーダー記法だけでは並列化可能割合やキャッシュヒット率なども評価できないために、最もよく見られる計算量評価の方法であるにも関わらず現実に即していないこともあります。しかしながら一般性の高い評価方法であることもまた事実です。

オーダー記法の問題点はあくまで広く使われている一方で、実運用で利用する際には留意すべき点が多いという点です。それらの注意点が頭に入っていれば、実計算時間とのずれに遭遇しても原因分析は難しくありません。

ゆえにオーダー記法を実際の評価に用いる際には上に挙げたような影響を考慮に入れつつ、計算速度の実測値と比較しながら用いることで、有用な評価軸の1つとして扱うことができるはずです。

7.参考文献

[1] 「ランダウの記号」(Wikipedia)
https://ja.wikipedia.org/wiki/ランダウの記号
(2025/08/10 参照)

[2] 「アムダールの法則」(Wikipedia)
https://ja.wikipedia.org/wiki/アムダールの法則
(2025/08/10 参照)