計算量のはなし - 赤い黒歴史を蓄積する

どうも華麗なるキャッツパーです。キャットアッパーです。
この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。

私は過去に、暇に任せてこのようなスライドを作ってしまいました。

有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。

本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。
計算量とはなんぞやということについては上のスライドを読んでください。

計算量の種類

競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。
最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから、これを指標に考えることが主でしょう。
償却計算量というのは、同じ処理をN回行った時に、1回あたりどれくらいの計算量になるかというものです。競技プログラミングではクエリ処理の問題でお世話になります。Union-Findでもこの概念が重要になってきます。
似たものとして平均計算量というものがあります。これは全ての入力パターンの平均をとったものです。償却計算量とのちがいは独立に行った時の平均をとるか、連続して行った時の平均をとるかです。

最悪計算量

最悪計算量の計算は容易です。ほとんどのアルゴリズムで、最悪な実行時間を与える入力パターンを自明に考えることができます。
基本的に全てのループを完全に処理すると考えて計算するとうまく行きます。足し算と掛け算で概算できます。
ただ、再帰関数は少してごわいです。ある入力パターンをあたえるとそれより小さめのパターンで同じ関数を呼び出すわけですから、ややこしいことになります。
基本的には、サイズNの入力を与えた時の計算量をF(N)などと置いて、関数方程式をとくことになります。

問1.以下のアルゴリズム(マージソート)の最悪計算量がO(NlogN)よりはやいか求めよ

まず、sort関数に長さNのリストを与えた時の計算量をF(N)、combine関数に長さの合計がXである２つのリストを与えた時の最悪計算量をC(A+B)とします。
それぞれを中の処理の計算量の和で表すと
F(N) = O(N) + 2 * F(N/2) + C(N)
F(1) = O(1)
C(X) ≦ C(X-1) + O(1)
C(1) = O(1)
こんなかんじです。
C(X) = O(X)であることは自明だと思います。というわけでそれを代入してFについて詳しくときましょう。
F(N) = O(N) + 2*F(N/2)
F(1) = O(1)
ここで、真面目に漸化式を解いてもよいですが、競技プログラミングするときに厳密な計算量は必要ありません。通るか通らないかが肝心なので期待する計算量を当てはめてみてうまくいくか確認するだけでよいでしょう。今回はO(NlogN)より速いかどうかしか気にしていないので、F(N)=O(NlogN)として代入して、左辺が右辺以上になるか確かめればよいです。
O(NlogN) ≧ O(N) + 2 * O( (N/2)log(N/2) )・・・①
O(N) + 2 * O( (N/2)log(N/2) ) = O(N) + O(N(log(N)-1)) = O(NlogN)
よって①は真
実践の場面ではO(N^2),O(N√N),O(NlogN)あたりを試してみればよいでしょう。

問2.以下のアルゴリズム(クイックソート)の最悪計算量がO(NlogN)よりはやいかを求めよ

さきほどよりスッキリしていて計算が楽に見えますが実はそんなことありません。マージソートはsortの中で再帰するsortに与える入力のサイズが決まっていましたが今回は未知です。
F(N) = max{F(A)+F(B)+O(A+B) | A+B = N}
F(1) = O(1)
さて、F(N)=O(NlogN)として代入して確かめてみましょう
O(NlogN)≧max{O(AlogA)+O(BlogB)+O(A+B)|A+B=N}
O(AlogA)+O( (N-A)log(N-A) )の最大値は微分すればわかりますが, A=1もしくはA=(N-1)のときです。ただ微分しなくても、AとBの対称性から、Aのとりうる値の端っこか真ん中のどちらかでF(N)が極値になるのだなということがわかりますので、3つを調べて結果を観ても良いでしょう。
A=1のとき右辺は
O(1log1)+O( (N-1)log(N-1) )+O(N)
O(1) + O(N)+ O( (N-1)log(N-1) )
これは明らかに十分大きいNでO(NlogN)より大きくなります。よってO(NlogN)ではありません。なおO(N^2)を代入してみるとうまく等号成立します。つまり最悪計算量はO(N^2)です。
なお、ここでいう「十分大きいN」というのが入力の制約の外である場合があります。そのときはその範囲内でO(NlogN)が成り立つことになります。そのようなことはあまり無いですが実践では注意しましょう。

問3.「木をマージする一般的なテク」の最悪計算量がO(NlogN)よりはやいか求めよ。

APIO2012の第一問「忍者の派遣」などで必要となるテクニックです。
ともかく、式を立ててみましょう。マージ関数に大きさNの部分木を与えた時の計算量をF(N)としましょう。
F(N) = max{F(A) + F(B) + O(AlogB)| A+ B = N, A ≦ B}
F(N)=O(NlogN)を代入してみると
O(NlogN) ≧ O(AlogA) + O( (N-A)log(N-A) ) + O(Alog(N-A))
クイックソートの時と同様に右辺を微分するとN = 2A(Aの値域の端っこ）のときに最大値を得ます。
3*O( (N/2)log(N/2) ) = O(NlogN)
よってうまく行きます。

償却計算量

償却計算量が高級に使われているアルゴリズムといえば、spray木やUnion-findやfibonacci heapですが、どれも有名なんでわざわざ計算量を解析するのは一度だけでよいでしょう。ただどれも難しいです。ここで説明するにはアルゴリズムから記述する必要があって面倒くさいので他のページをあたってください。fibonacci heapは日本語版wikipediaに詳しくかかれております。
この記事では上記のアルゴリズムの償却計算量解析によく使われる手法ポテンシャル解析を解説したいと思います。
ポテンシャル解析ではデータ構造の状態にたいして値を対応付けるポテンシャル関数というものを使用します。
ある操作をすることで実際の実行時間O(N)で状態をAからBにかえたとします。ポテンシャル関数をPとすると、このときの償却計算量はO(N)+P(B)-P(A)です。
このようにすると何が嬉しいかというと、たくさんの操作をしても、最初と最後のポテンシャル関数の値さえわかれば、あとは償却計算量だけで計算できるということです。つまり、たとえば償却計算量がO(N)操作をして、状態Aを状態B,C,Dを経て状態Eにしたとします。そのときの実際の実行時間はわかりません。しかし式を立ててみると
(O(?) + P(B) - P(A)) + (O(?) + P(C) - P(B)) + (O(?) + P(D) - P(C)) + (O(?) + P(E) - P(D)) = 4O(N)
整理するとなかのポテンシャル関数の値が打ち消し合って
O(?) + P(E) - P(A) = 4O(N)
つまり、途中経過がどうであろうと、最初と最後と、途中で行った走査の償却計算量の和だけで実際の実行計算量を求めることができます。このときもしP(E)-P(A)が充分小さいとすると実際の実行計算量と償却計算量を同じとして考えることができます。　うれしい！

問1.つぎのデータ構造(動的にメモリを確保する配列)に値を追加するときの償却計算量を求めよ。

URL:https://gist.github.com/catupper/7838399
pythonっぽい擬似コードですが、ようするに

予め確保していたサイズより大きくなろうとしたら、その二倍のメモリを確保してから値を追加する。
そうでないならば普通に値を追加する。

つまり
n = 現在持ってる値の数
N = 現在確保しているメモリの数として

n=NならばNを二倍にして値を追加
そうでないならば普通に追加

という処理をするものです。
最悪計算量はもちろんO(N)です。前者のタイプだとO(N)かかってしまいます。しかし時にはO(1)なので償却計算量はもう少し小さくなるかもしれません。
ここで配列の状態Xに対するポテンシャル関数を以下のように定義します。
P = 2n - N
それでは、add関数の各場合について償却計算量を求めてみましょう。
n=Nの場合
実際の計算量は先ほど出したとおりNです
ポテンシャル関数の値は 2N-N から 2(N+1)-2Nになりますので償却計算量は
N + (2(N+1)-2N) - (2N-N) = 2
n≠Nの場合
実際の計算量は1でnが1増えます
1 + (2(n+1) - N) - (2n - N) = 3
よってどちらの処理も償却計算量はO(1)となります。
さて、何もない状態からX個値を追加した時の計算量を考えてみましょう。
ポテンシャル関数の値は0から2X-Nに増えていますので最大でX増えることになります。
add関数の償却計算量はO(1)ですのでX回行うとO(X)です。
よって実際の計算量はX+O(X) = O(X)ということになります。
これの平均をとると、やはりadd1回あたりの計算量はO(1)ということになります。やったね！

これがポテンシャル解析です。競技プログラミングにおいてはしゃくとり法のようなアルゴリズムの計算量解析に使えると思います。探索終了前と探索終了後のポテンシャルの差と償却計算量で考えるのです。

計算量が厄介な問題

最後に計算量をうまく考えないといけない問題をいくつか載せます。みなさんもぜひ、計算量を意識して問題を解いてみてください。
NPCAJudge#26 私を月に連れてって・・・再帰関数の最悪計算量の漸化式を解くとうれしい。
JOI春合宿2012,Day1　ビルの飾り付け2・・・例のマージテクです。
第19回POI Stage1 Well・・・あるところで償却計算量がわかると速いです。