コラム: 複数変数関数のビッグオー、考えたことありますか？
アルゴリズムのほとんどの教科書では関数のビッグオー記法は以下のように定義される：
定義（ビッグオー記法）
二つの関数 $f,g\colon \Nat\to\Real_{>0} $ に対し、以下が成り立つとき、$ f(n)=O(g(n)) $ と表す： 二つの定数$ c>0,N\in\Nat $が存在して、任意の$ n\ge N $に対して
$ $ \begin{align} f(n) \le c\cdot g(n). \end{align} $ $
これは、十分大きな$ n$では $f(n)$ が$g(n) $の定数倍で抑えられることを意味し、二つの関数の増加速度を比較するために用いられる記法である。 他にも漸近評価を表す記法として$ \Omega(\cdot),o(\cdot),\omega(\cdot),\Theta(\cdot) $がよく用いられる。
$ f(n)=O(g(n)) $における「$ =$」は数学における等号ではない。一般に等号は反射律 （ $a=b$ ならば $b=a$ ） が成り立つが、例えば $O(n^2)=n$ は成り立たない。一つの解釈の仕方としては、「右辺」の $O(g(n)) $ を集合とみなし、$ f(n)\in O(g(n)) $ とみなすことができる。しかしながら、アルゴリズムの計算量や確率不等式の文脈では、
$ $ n^{O(1)},\quad \exp(-\Omega(n)) $ $
などのような表記を用いて時間計算量や集中不等式などの漸近的な評価を記述することも多々ある （厳密にはこれは記号の濫用ではあるが） ので、ビッグオー記法は集合を表すというスタンスで読み解くと不都合が生じることもある。
基本的には私はこういったことに関しては「こうであるべき」 という思想は持たず、その時々で便利な考え方を採用するようにしている。ビッグオー記法の場合、$ O(g(n)) $ といえば、$ n$ に依存しないある定数 $c>0 $ に対して$ c\cdot g(n) $ で上から抑えられるという何らかの一つの値を意味しており、文脈によって集合と解釈した方が便利なときはそうするようにしている。他にも確率変数そのものが何なのか扱いについてもこのスタンスである。
本題に戻る。多くのアルゴリズムの教科書では上のように、一変数関数$ f\colon\Nat\to\Real_{>0} $に対してのみビッグオー記法を定義し、最短経路アルゴリズムあたりの章で、ヒープを用いたダイクストラ法の解説をするとなぜか突然
$ $ \begin{align} O((m+n)\log n) \end{align} $ $
のような記法が定義もなしに現れるのである。ここで$ m,n $はそれぞれ入力として与えられるグラフの辺と頂点の個数を意味する。
我々はビッグオーは定数倍を除いた関数の増加スピードを図る指標であることをすでに知っているので、これを見ると脳内では、十分大きな定数$ c>0 $に対して、アルゴリズムの計算ステップ数が
$ $ \begin{align} c\cdot (m+n)\log n \end{align} $ $
で抑えられると解釈して飲み込んでしまう。 もちろんこれは、一変数関数に対するオーダー記法を二変数に自然に拡張した概念であるのだが、その形式定義について気にしたことはあるだろうか？
本稿では、「一変数から複数変数への拡張」に焦点をあてているため、以降は簡単のため二変数関数に絞って議論を進めていく。
最初に思いつく定義
多くの人が最初に思いつくであろう定義は「全ての変数の値が十分大きいときに定数倍で抑えられる」という定義であろう。これを本稿では便宜上and型の定義と呼ぶことにする。
定義1（and型の定義）
二つの関数$ f,g\colon\Nat^2\to\Real_{>0} $に対して、以下が成り立つとき、$ f(n,m) = O_{\land}(g(n,m)) $ であるという： ある定数$ c>0,N\in\Nat $が存在して、
$ $ \begin{align} n\ge N\text{ かつ }m\ge N \end{align} $ $
を満たす任意の $ (n,m) $ に対して、$ f(n,m)\le c\cdot g(n,m) $ が成り立つ。
ところが、この定義だと
$ n$が小さくて $m$ が大きい場合は、定数倍で抑えられている必要がない
ということになる。例えば関数
$ $ \begin{align} f(n,m) = \begin{cases} n+m & \text{if }\min(n,m)\le 100,
1 & \text{otherwise} \end{cases} \tag{1} \end{align} $ $
とすると、$n $ と$ m$が十分大きいときは必ず $f(n,m)=1$ となるため、 $f(n,m)=O_{\land}(1) $が成り立ってしまう。これは、$ O(1) $ ならば有界であってほしいというような我々の直感とは反してしまう。
別の定義
先ほどの例は、$ n$ と $m$ の両方が十分大きい時に抑えられるという性質がよくなかったのであって、これを鑑みると「 $n$ と$m $の少なくとも一方が十分大きい時に抑えられる」とすれば良さそうに見える。これをor型の定義と呼ぶことにする。
定義2（or型の定義）
二つの関数$ f,g\colon\Nat^2\to\Real_{>0} $に対して、以下が成り立つとき、$ f(n,m) = O_{\lor}(g(n,m)) $ であるという： ある定数$ c>0,N\in\Nat $が存在して、
$ $ \begin{align} n\ge N\text{ または }m\ge N \end{align} $ $
を満たす任意の $ (n,m) $ に対して、$ f(n,m)\le c\cdot g(n,m) $ が成り立つ。
この定義に基づくと、式(1)で定義した関数は$ f(n,m)=O_{\lor}(1) $にはならず、$ f(n,m)=O_{\lor}(n+m) $ が成り立つ。
私は今のところ、この定義で困ってしまう例が見つかっていないのでこの定義で満足している。
しかしながら、$ n$ や $m$ が$0 $をとりうるような設定だと
$ $ nm+1 = O_{\lor}(nm) $ $
が成り立たなくなってしまう！（一方の変数の値が十分大きくても、もう一方の変数を$ 0$に設定することで右辺は $0$ にできるが、左辺は常に $1$ 以上だから）。 しかし、考える関数の引数に $0$ を考えることはほぼなく、基本的に $n,m\ge 1$ とする場合がほとんどなので、私はこの例は気にしないことにしている。
。 。 。
と思っていたのだが、チャーハンを作っているときに困ってしまう例を見つけてしまった。$O_{\lor}(\cdot) $ に基づくと
$ $ 1 = O_{\lor}(m\log n) $ $
が成り立たなくなってしまう！（$ n=1 $で$ m\to\infty $としていっても右辺は常に$ 0$だから） 一応、定義2では関数の値域を正にしているので、形式的には当てはまらないのだが、$O(m\log n) $ という記法は非常によく出てくる評価なので、式（1）と比べればこちらの方が非常に困ってしまう。 こんなことを考えながらチャーハンを作るものだから油を入れすぎてしまった。
他にも
$ $ O(n)\cdot O(m) = O(nm) $ $
というよくある計算については、左辺は $ O( $一変数関数$ )$ の積であるため、$n $ と$ m$は両方とも十分大きいところでの評価となるが、もし右辺を $O_{\lor} $ で解釈すると両辺の意味合いが異なってしまう。
これらのことから、個人的には「デフォルトはand型で捉えていき、困る場面に出会したらその都度に適切な定義を適用する」が落とし所なんじゃないかと思っている（やはりほとんどの人はこのように考えるだろうし）。 or型とand方の他にも
任意の固定した$ m\in\Nat $に対して $ O(g(n,m)) $であることを省略して $ O(g(n,m)) $ と表す
という文脈（例えばパラメタ化計算量（parameterized complexity）の文脈で $ O(n^k)$ と表した、このような意味合いで用いられることがある）もあるので、常に一つの定義で解釈するのは良くないという、無難な結論に落ち着く。 そして、普段使いとは異なる定義で漸近的な記法を用いるときは、本来はそれを明記すべきだと思う。
補足
世界にはこの疑問について気にしていた人はそれなりにおり、stack exchangeで見るとこのような質問がいくつも見つかる。その中でRodney Howellによる
On Asymptotic Notation with Multiple Variables
という論文で細かく議論されているので、興味のある人はぜひ電車の中とかで読んでみてほしい。要するにどのような定義を採用したとしても、直感的にオーダーが満たしてほしい性質（著者が挙げた五つの性質）のどれかは成り立たない、ということを示している。