アルゴリズムとデータ構造#1 速いアルゴリズム、遅いアルゴリズム

はじめに

本記事は、「アルゴリズムとデータ構造」コースの第一回となります。全体の概要については、イントロダクションをご覧いただくのがよろしいかと。

対象読者(本記事)

以下のどれかにあてはまる方を対象にしています。一つも当てはまらない場合は、[次の記事]に行かれてもよいかもしれませんね。

• 「アルゴリズム？なんだそれは！？」ってひと

• 「計算量？なんだそれは！？」ってひと

• 「Big-O記法？なんだそれは！？」ってひと

アルゴリズムとは何か

アルゴリズムとは、入力を受け取って、何らかの処理を行い、出力を返すものです。……どういうことだ？

例えば、入力として整数の配列を受け取り、その配列の要素の和を知りたいとしましょう。「配列」の細かな性質については、今度またやります。
さて、pythonの例をお見せしましょう。pythonが読めなくてもノリで読めますよ。配列arrを受け取り、その要素を全部足したresという変数を返しています。

def sum(arr):
    res = 0
    for x in arr:
        res += x
    return res

……しょうもないですね。このアルゴリズムは、入力の配列の長さに比例して計算量が増えていきます。だって、foreachで配列をそのまま回していますからね。

Big-O記法

アルゴリズムの計算量を表すのに、Big-O記法というものがあります。これはアルゴリズムの計算量を、入力の長さに対してどのくらい増えるかで表すものです。

例えば先ほどのアルゴリズムは、入力の長さを$${n}$$とすると、計算量は$${\mathcal{O}(n)}$$と表されます。これは$${n}$$が大きくなるにつれて、計算時間が$${n}$$に比例して増えていくことを表しています。読み方としては、例えば「このアルゴリズムの（時間)計算量のオーダーは$${n}$$なのか～」みたいな感じです。なお、同じ問題を解くアルゴリズムA,Bがあったときに、Aのほうが$${\mathcal{O}(n)}$$でBのほうが$${\mathcal{O}(n^2)}$$であるような場合には、AはBよりも計算量のオーダーが優れている みたいなことを言います。

細かいけど気にしたいBig-Oの定義(コラム)

Big-O記法は、以下のように定義されます。

$${f(x) = \mathcal{O}(g(x)) \Leftrightarrow ある定数cとx_0が存在して、x > x_0ならば，|f(x)| \leq c|g(x)|が成り立つ．}$$

例えば、$${f(x) = 2x^2 + 3x + 1}$$という関数があったとき、$${f(x) = \mathcal{O}(x^2)}$$が成り立ちますね。
計算量の話でいえば、$${f(n)}$$がこのアルゴリズム(入力長が$${n}$$のとき)の計算量になるとき、$${g(n)}$$がこのアルゴリズムの計算量の上界になるということです。まあざっくり、競争相手に負けないくらい強い関数ってことです。

ということは、さっきのアルゴリズムの計算量は$${\mathcal{O}(n)}$$と表されますが、$${\mathcal{O}(n^2)}$$と表すこともできますよね．
$${\mathcal{O}(n)}$$のほうが強い(より速さが伝わる)表現となります。せっかくなので強い表現を使ったほうがアルゴリズムの良さをアピールできますから、まあ普通は$${\mathcal{O}(n)}$$と表現します。

計算量がすべてではない

計算量がすべてではないということを説明するために、以下のアルゴリズムを考えます。

import time
def sum(arr):
    res = 0
    time.sleep(1)#最初に1秒寝る。なんか重い処理のつもり
    for x in arr:
        res += x
    return res

と

import time
def sum(arr):
    res = 0
    for x in arr:
        time.sleep(1)#毎回1秒寝る。なんか重い処理のつもり
        res += x
    return res

のアルゴリズムがあるとしましょう。これらはどちらも$${\mathcal{
O}(n)}$$といえそうですね。……ということは、どちらも同じくらい良いアルゴリズムなのでしょうか？いやー、どう考えてもそんなことはありません。
前者は一回だけ長い時間待ってから計算を始めますが、後者は毎回毎回待ってから計算を始めます。明らかに前者のほうが速いはずです。ですが、こんなに単純な関数の実行の違いであるにもかかわらず、Big-O記法では同じオーダーの計算量として扱われてしまいます。

今回はかなり極端な例を挙げましたが、実際には以下のようなことが起こりえます。

• アルゴリズムAはオーダーでは勝っているが、特に入力が大きくないときにはオーダーで負けているアルゴリズムBのほうが速い

  • 現実の問題で実行してみて速いほうが正義

• 時間的な計算量では勝っているが、メモリを大量に消費してしまう

  • 実際の計算機で動かせないアルゴリズムは無意味

などなど、まあ基本的には速いほうがえらいのですが、実務上ではいろいろと考慮することがありますので、オーダーは一つのものさしに過ぎないということを覚えておいてください。今後、「オーダーでは確かに速そうだけど、実務上はほとんど使われない」みたいなアルゴリズムも紹介する機会があるかもしれません。

でも大体オーダーが偉いよ

混乱させるようで申し訳ないのですが、それでも大抵の場合、オーダーが正義 であることは間違いありません。深い理由がない限り、$${\mathcal{O}(n^3)}$$のアルゴリズムよりも$${\mathcal{O}(n^2)}$$のアルゴリズムを使うべきです。コーディング面接でも「今書いたアルゴリズムの計算量は？」と聞かれるでしょうし、自分が書いているアルゴリズムの計算量オーダーは常に認識しておくべきです。これからの記事でも、何度も登場しますよ。

まとめ

• アルゴリズムとは、入力を受け取って、何らかの処理を行い、出力を返すもの

• Big-O記法は、アルゴリズムの計算量のオーダーを表すもの。 入力長が大きくなるにつれて、計算時間がどのように増えていくか を表す

• Big-Oがすべてではないが、速さの指標として有用 である