オーダーを極める思考法：最強最速アルゴリズマー養成講座（1/3 ページ）

プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。

[高橋直大，ITmedia]

プログラムの実行時間

　業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？　非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。

TopCoderの制限に関して

　TopCoderでは、実行時間およびメモリ使用量の制限は以下のようになっています。

• 実行時間：1テストケースにつき2秒
• メモリ使用量：64Mバイト

　このうち、メモリ使用量は、最初はあまり気にする必要はないでしょう。TopCoderの環境ではint型が32ビット、つまり4バイトですので、例えば要素数が10,000,000（1千万）個のint型配列であれば約38Mバイトとなります。ここで、要素数が20,000,000個となると約76Mバイトとなるので、メモリ使用量の制限を超えてしまう、ということが理解できれば十分です。そもそもTopCoderではそこまでメモリを使うことはあまりないと思います。

　問題は実行時間です。プログラムの実行時間に対して正確な認識を持つことができれば、ある方針を思いついた時に、制限時間に間に合うかどうかを判断できますし、Challenge Phase（Challenge Phaseについては前回の記事を参照ください）では、他人のソースコードが制限時間を超過しているかどうかを判断できるので、勝負を有利に進めることができます。実行時間に対する感覚はしっかりと養っておきたいところです。

　ここで、TopCoderのサーバ上での実行時間を計測するために、以下のようなソースコードを作成しました。

        DateTime dt; TimeSpan ts;
        long a = 0;
        dt = DateTime.Now;
        for (long i = 1; i <= 10000000; i++) ;
        Console.WriteLine("Time: " + (ts = DateTime.Now - dt).TotalMilliseconds + "ms (ループのみ)");
        dt = DateTime.Now;
        for (long i = 1; i <= 10000000; i++) a += i + 10000000;
        Console.WriteLine("Time: " + (ts = DateTime.Now - dt).TotalMilliseconds + "ms (足し算)");
        dt = DateTime.Now;
        for (long i = 1; i <= 10000000; i++) a += i - 10000000;
        Console.WriteLine("Time: " + (ts = DateTime.Now - dt).TotalMilliseconds + "ms (引き算)");
        dt = DateTime.Now;
        for (long i = 1; i <= 10000000; i++) a += i * i;
        Console.WriteLine("Time: " + (ts = DateTime.Now - dt).TotalMilliseconds + "ms (掛け算)");
        dt = DateTime.Now;
        for (long i = 1; i <= 10000000; i++) a += 10000000 / i;
        Console.WriteLine("Time: " + (ts = DateTime.Now - dt).TotalMilliseconds + "ms (割り算)");

　このソースコードは、それぞれ、ループのみ、足し算、引き算、掛け算、割り算の5種類の演算を10,000,000回行うループに対して、それぞれ実行時間を計測するだけのプログラムです。これをTopCoder上のサーバで動かすと、実行結果は次のようになりました。

Time：15.625ms（ループのみ）

Time：31.25ms（足し算）

Time：31.25ms（引き算）

Time：46.875ms（掛け算）

Time：93.75ms（割り算）

　このプログラムはC#で記述しました。C++を用いるともう少し早くなるかもしれませんが、大きな差にはならないと思います。今回はループの中身が非常にシンプルですが、実際のプログラムではもう少しループの中身が複雑になりますので、前記を踏まえた上で、

• ループの最も内側の計算数が10,000,000（1千万）程度であれば、ほとんどのプログラムで問題なく間に合う
• ループの最も内側の計算数が100,000,000（1億）程度になると、複雑な計算をしている場合はかなり注意する必要がある

くらいの認識を持っておくとよいでしょう。

計算量の「オーダー」とは？

　こうした時間の計算は、計算量の「オーダー」と呼ばれ、O記法を用いて表現されます。例えばn回のループの内側にm回のループが入っている場合、O（n*m）と表記します。この場合、一番計算回数が多い個所の計算回数がn*m回である、という程度に理解してもらえれば結構です。計算量は次数の一番大きい項に大きな影響を受けます。n^5 + n^3のような多項式を例に挙げると、nが大きくなればなるほどn^5とn^3の差は大きくなり、おおよその計算量をつかむのであれば、n^5の部分のみを考えればよいことが分かります。つまり、この場合の計算量のオーダーは、O（n^5）と表現できます。このように、次数の一番大きい項をO記法で表現しておおよその計算量をつかむのが、計算量のオーダーであるといえます。

　この計算をする際に、今回は単純な四則演算だけでしたが、ほかの関数を呼び出す場合や、特別なデータ構造に対して操作を行う時などは、その操作や関数の計算量を把握しておかないと計算がズレてしまいます。例えば、n個の配列をソートしようとすると、O（n*logn）程度の計算量となりますし、n個要素を含んだリスト構造から真ん中の要素を取り出したい、といった時は、O（n）掛かってしまいます（厳密にはn/2回ですが、計算量を計算する際には、定数倍の係数は基本的に無視して表記します）。

　計算量というのはなじみのない方には分かりにくい概念かもしれませんが、オーダーについては今後の連載でも登場しますので、少しずつ覚えていけばよいでしょう。

　それでは問題に移りましょう。今回はSRM443 Mediumの問題に取り組んでみます。