アルゴリズムを学びはじめてみた

最近はアルゴリズムを勉強している。

なかなか頭に入ってこないので、アウトプットをして整理する。

なお、言語はGoで書いている。

• アルゴリズムとはなにか？ ⇒「問題を解くための方法,手順」のことを指す。

たとえば、「FizzBuzz問題」や「自動販売機お釣り計算」を解くのにもアルゴリズムが使われるし、アルゴリズムといえば・・・？で、頻繁に出てくる「探索問題」や「グラフ問題」を解くのにもアルゴリズムが使われる。

ためしに「FizzBuzz問題」を解いてみる。

package main

import (
    "fmt"
    "strconv"
)

func FizzBuzz(i int) string {
    if i%15 == 0 {
        return "FizzBuzz"
    } else if i%5 == 0 {
        return "Buzz"
    } else if i%3 == 0 {
        return "Fizz"
    } else {
        return strconv.Itoa(i)
    }
}

func main() {
    fmt.Println("1から標準入力から入れる値(INPUT値)までの数を順に出力するプログラム。\nただし、3の倍数のときは数の代わりに「Fizz」5の倍数のときは「Buzz」3と5の両方の倍数の場合には「FizzBuzz」を出力する。")
    fmt.Print("INPUT:")

    var n int
    _, err := fmt.Scan(&n)

    if err != nil {
        fmt.Println("err: INPUT.")
        return
    }

    for i := 1; i <= n; i++ {
        fmt.Println(FizzBuzz(i))
    }
}

「FizzBuzz問題」程度であれば、解き方の種類がそれほど多く存在しないが、難しい問題を解いた時、自分の書いたアルゴリズムがはたして良いアルゴリズムなのかどうかが判断できない。

その判断の材料となるのが、計算量である。

• 計算量とは何か？ ⇒ 「コンピュータ上での実行に要する時間」のことを指す。

計算量がわかれば、実装しようとしているアルゴリズムがコンピュータ上でどの程度時間を要するのか、あらかじめ大雑把に見積もる事ができる。

ある問題に対して、2種類の解き方を思いついたときに、どちらの方がより優れたアルゴリズムなのかが計算量によって判断できるので、計算量は非常に重要な考え方となる。

たとえば、以下のような「年齢当てゲーム」の場合を想像する。

Aさんの年齢を当てたいと思います。

Aさんの年齢が20歳以上36歳未満であることはわかっているものとします。

Aさんに複数回「Yes / No で答えられる質問」をすることができます。

何回の質問で、Aさんの年齢を当てることができるでしょうか？

この問題は有名で、解き方は大きく2つある。

1つは「Aさんは20歳ですか？」「Aさんは21歳ですか？」・・・と、年齢を当てるまで順番に繰り返す方法

もう1つの解き方は、「Aさんは28歳以上ですか？」と、真ん中で切手片方に絞っていく方法

前者の方法を線形探索法、後者の方法を二分探索法と呼び、以下の通り質問回数が変わってくる。

• 線形探索法: 17回
• 二分探索法: 5回

年齢の範囲が「20歳以上36歳未満」という前提条件があるため、質問回数の差は少ないが、前提条件の範囲が大きければ大きいほど2つの差は大きくなる。

計算量を数値で表現するのには限界がある。

先程の「年齢当てゲーム」程度の問題であれば、線形探索法を使えば17回、二分探索法を使えば5回。とか言えるが、前提条件の年齢の範囲が大きくなると、「なんか線形探索法の方が質問回数が増えそう・・・」くらいしか言えず、数値での表現に限界がでてくる。

そこで出てくるのが、O記法（オーダー記法）。

というわけで、次回はO記法（オーダー記法）について書く。