計算量オーダーを考えることは、ボトルネックを考えることだ

とてもみじかい記事です

要約

「計算量オーダー $O(N)$」¹ は
計算量そのものを表現する以上に
速度的ボトルネックの特定/解消に役立つ、実用的な考え方だぜ²

どういうことなの

プログラミングにおいて、ある処理にかかる計算量は、オーダー記法によって表現されるのが一般的でしょう。

$O(N)$
このように表記される類のもの

基本情報技術者試験の出題範囲でもあるように、知識領域としてはメジャーで、概要を知っている方が多数のはず。

『計算量オーダーは処理の計算量をおおまかに表現するものである』

オーダー記法による計算量表記の説明として、上記は正しいでしょうし、このように案内されることは多いように思います。
一方で、この表現が何に役立つのか という実用的な側面についての説明は、あまり多くないように見受けます。このせいで、実用されない「物置にしまった知識」になるケースが、それなりに発生しているのではないかと勝手に推察しています³。

計算量オーダーを考えることは、(速度的)ボトルネックを考えることだ

オーダー表記で計算量を表現する場合、
①一連の処理を構成する部分処理の計算量を把握し
②もっとも遅さに貢献する具体的な処理を特定する
というプロセスを踏みます。

いいかえれば、『計算量オーダー』には 算出の過程に、プログラムのボトルネックを検証する視点を含む という側面があります。

この側面をふまえれば、計算量オーダーの算出をとおして ボトルネックを発見するまなざしを養う ことや

計算量算出 -> ボトルネック箇所のプログラム修正 -> 計算量算出(改善結果チェック) -> ボトルネック修正...

のような プログラムの改善サイクルを静的に回す ことが可能になります。

『計算量オーダー』はたしかに計算量の表現自体でしかありませんが、
利用を通してプログラムのボトルネックへの解像度が上がり、具体的なアクションにも繋がりうる という点で、身近で実用的なメリットのある考え方なのです。

むすび

計算量オーダーってみんな学ぶわりにあまり使われてないな…という印象があったので
でもじつは競プロみたいな尖った環境でなくても便利に使えるんだぜ！という雰囲気を発信したいだけの記事でした。

個人的にも、計算量オーダー知ったのはエンジニアなりたての頃だった筈なのに
実用レベルまで消化して使役してこれなかった反省があったので
知識の整理ついでに、誰かの理解をブーストしえる素材として書き起こしました。

知識の引き出しハードルが低くなれば本望です。知識は使ってナンボだとおもいます

---

1. この記事では「計算量オーダー」という言葉を「オーダー表記による計算量表現」の意味で使っています。また、「計算量オーダー」を象徴的に表現する記号として O(N)を使っています。オーダー記法での計算量表記 != O(N) です。ほんらいN部分には、N^2だのNlogNだの、表記対象の処理の計算量を表現する数式が入ります。 ↩

2. 「計算量を把握する目的は速度改善のためのみ」ではなく、とうぜんほかの側面からも用いられえます。たとえば、計算量が多ければ往々にしてメモリ消費量も多くなるでしょうから、メモリ消費量改善にも用いられえます。ただ速度改善の文脈で引き合いに出されることが経験上多いので、今回は速度に限定して書いています。 ↩

3. 競プロガチ勢は物置どころか枕元に置いて毎日一緒に寝るらしいです ↩