ビッグオー記法・計算量
アルゴリズムの効率を計る方法（日本語と英語で）
Click here for the English version.
プログラミングの基本を勉強していた26歳の私が、初めてコンピューターサイエンスの「アルゴリズム」を聞いたときに、肝を潰しました。毎日夕方になると、パソコンを閉じながら、「もっと高校の数学に集中すべきだった」、「父さんの会社の技師たちがアルゴリズムに苦労しているから、僕なんて無理だ」などとくよくよしました。
私のようなプログラミングの初心者たちは、「オーダー記法」や「時間計算量・空間計算量」のような言葉を聞けば、恐ろしく感じ、自信喪失する方が多いかもしれません。しかし、私にとって、少しぐらいの数字と論理の知識を持ちさえすれば、アルゴリズムの概要は誰でも理解できるものだと信じています。
このブログをもって、アルゴリズム記法の基礎を、読者の皆様にご紹介させていただきたいと思います。自分のプログラミングのレベルと規模が向上するにつれてよく現れるコンセプトの一つ：
ビッグオー記法（Big-O）
ビッグオーの定義
簡単に言うと、ビッグオー記法とは、プログラマーがアルゴリズムの効率を表現する方法のことです。そしてアルゴリズムとは、単にある問題の解決策のことです。それでは私たちの関数の効率は、一体どう計算すればいいのでしょうか。また、その方法はなぜ必要なのでしょうか。
関数かメソッドを定義するとき、同じ問題を解決するには、複数の実装方法があるはずです。下記のJavascript関数をご覧ください。reverseStringという関数は、与えられた文字列stringから逆転した新しい文字列を返します。
文字列の逆表示の関数を書き、テストが成功した後、そのままでいいと思う方もいるかもしれませんが、上記の実装は次の同じ関数と比べてどうでしょうか。
この三つ目は？
どれも同じ機能を果たすならば、「一番良い」実装はどのように決定するのでしょうか。コンピューターの出力速度をミリ秒で計ればいいのでしょうか。コードが一番短いので二つ目が良いのでしょうか。なぜ一番を決めなければならないのでしょうか。
この問題を解くのは、ビッグオー記法の用途です。的確な言語を使い、コードの性能について語り、様々な実装の良し悪しも観察することができます。また、コードをデバッグするときに容易く非効率な部分を見出せることも、ビッグオーの強みの一つです。
ビッグオーの計り方
もう一度前の例を見てみましょう。あるプログラムの性能を測るために、実時間演算を使えばいいのでしょうか。この方法では、15年の古いパソコンは最新式のMacBook Proと比べればどうなるでしょうか。たとえ同じブランド、同じ型、同じ年のパソコンを二台比較するとしても、全く等しい演算が手に入れられないのではないでしょうか。より良い方法があります。
ビッグオー記法は、実時間演算ではなく、パソコンの実行する単純な演算を数える計算です。概して言えば「時間計算量」と「空間計算量」を通し、ビッグオー記法を使用します。
次はこの足し算の関数をご覧ください。1から引数の数字 n まで、全ての整数を足して返す機能です。
ビッグオー記法の面から分析しましょう。for文の中で、変数 i を設定し、処理を繰り返すごとに値が増加します。そのfor文のブロックの中では、最中の条件式（i <= n）が成立しなくなるまで、i の現在値を総計の変数 sum に足します。この場合、実行する単純な演算の総数は計算できるのでしょうか。
そうです！n の値をもってできます。
i に初期値1を設定し、 n の値になるまで繰り返すごとに値が増加します。そして n の値により、演算の数も決定できます。これはビッグオーの時間計算量を示すものです。つまり、関数addUpToの時間計算量はO(n)となります。ランタイムの効率が n とともに多少変化するというわけです。
addUpToの別の実装はこちらです。
今回先ほどのfor文の繰り返し処理を使わなくなったので、演算の数「掛け算一つ(*)、足し算一つ(+)、割り算一つ(/)」は n の値にかかわらず一定しています。その結果、for文を使うaddUpToと比べれば一定数の演算を持っています。これはO(1)という時間計算量です。「定数時間」とよく呼ばれています。
時間計算量と空間計算量
さて、引数の値によるアルゴリズムのランタイムを示す時間計算量を習得しましたが、もう一つの計算量は？空間計算量とはアルゴリズムを実行するため、コンピューターのメモリの量を計算することです。要するに、そのプログラムの実行に必要なメモリの容量です。
関数sumArrayでは、数字が入っている配列を受け、全ての要素を足した総計を返します。
以上から、sumArrayは時間計算量のO(n)を持つことがわかってもらえると思います。arrayにある要素の数「ビッグオーの n 」 が増えるにつれて、for文の繰り返すループも蓄積されていきます。ところが、引数の値も繰り返し処理の頻度も、空間計算量を測るのとは関係ありません。「引数の値を除いて測ることを、正確に副空間計算量と呼びます。」
アリゴリズムに必要な容量を計算するには、まずその関数にある数字、文字列、配列といった変数を分析してみます。数値型、文字型、ブール型などの単純なデータ型の場合、O(1)の空間計算量があります。その一方Javascriptの配列、文字列、オブジェクトの場合では、データの大きさによるO(n)の空間計算量になります。
sumArrayの中の変数を集めるとこうなります。
変数arrayが引数なので、空間計算量とは関係ないことにご注意ください。それを含めた場合、O(n)の空間計算量になっていましたが、引数なので触れないことにします。そして、関数sumArrayの実装はO(n)の時間計算量と、O(1)の空間計算量を持っています。仮に関数の中で他の文字列や配列などの変数を設定するとしたら、まさしく計算量が両方O(n)になります。
ビッグオーの用途
プログラムの計算量を表すとき、詳細ではなく、一般の動向が優先されています。結局のところ、ビッグオー記法そのものは、「あやふやな数え方」に他なりません。的確な計算より、概算を通してアルゴリズムの効率を判断するものです。ある変数 n の値の増減に伴う動向を計ることを、ビッグオー記法と言います。
効率の動向により、そのアリゴリズムの実行も大幅に変化する可能性があります。
効率の昇順から、最もよく現れる計算量は：
- O(n²)
- O(n log n)
- O(n)
- O(log n)
- O(1)
ビッグオー記法は最悪の事態に集中します。例にとり、もう一度addUpToをご覧ください。
もし引数 n の値に1を設定するとしたら、そのfor文のループは一回実行してからすぐに返すはずです。理想の定数時間ができたとは言えるのだが、これはビッグオーの目的ではありません。「この場合では、Ω(1)となります」。プログラマーとしては、高機能な実装を書いたり、きっちり効率を計ったりするためには、その最悪の事態を備えなければなりません。
アルゴリズム のビッグオーを計るには、妥協が必要です。もちろん、O(1)の計算量に及ぶ関数を書ければ理想です。しかし、例えて言うと、この関数を実装するためには、ソートをしておいたデーター構造が必要になります。この構造の中では何万か、何十万かもの要素が入っているとしたら、関数を実装する前にソートし、オーダー記法はどうなるでしょうか。それはソートしていないデーター構造を使い、普通のO(n)の計算量に及ぶ関数より、実技できるのでしょうか。こういう複雑な面を鑑みるのが、プログラマーそれぞれの甚大な責任だと思います。
まとめ
ビッグオー記法を身に付けるとともにJavascriptのメソッド、関数などの開発も上達していきます。計算量というと、必ず一番効率の良いアルゴリズムを取得するべきだというわけではありません。一般的にはO(n)以下の計算量に達すれば、十分だと言えるでしょう。時間と空間の効率を通じ、我々のプログラムの知識を少なからず深めるのが真の狙いです。
ビッグオーだけの場合、単なるアルゴリズムの基本を表していますが、この基準から、Javascriptといったコンピューター言語の理解も深まると言えるのではないでしょうか。