#4 アルゴリズムの正しさ

日曜技術研究所

巷ではよく「弊社独自アルゴリズムでトレードすることで、…」といったものが散見される。『ヘイシャドクジアルゴリズム』とはなにか。また、『アナタドクジアルゴリズム』を作成してみよう。の回です。


アルゴリズム

アルゴリズムとは、

問題を解くための手順を定めたものである。

石畑清(1989)アルゴリズムとデータ構造　岩波書店

つまり、数学の関数から料理のレシピを含意できる。コンピューターには関係ないように思えるが、以下のように考えると納得がいく。

レシピには、具材の量が明記されている。また、どう切るか。どう炒めるかや、何をどのタイミングで入れるとすべての手順が記されており、『どう作るか』を『手順』によって解決していることになる。

以上を、引用に当てはめてみると、『レシピとは、「どう作るか」を「手順」によって解決している』と言い換えられる。

正しさの条件

当然、レシピにも正しさが必要である。

1.お皿に乗せるのは、完成品だけである。
2.レシピが必ず終わること。

つまり、肉じゃがを作りたいのに、切っただけのジャガイモとニンジンが完成品として、お皿に盛られても正しいレシピとは言えないだろうし、「僕のお母さんは、肉じゃがを作り始めてもう三年がたちます。」となってもレシピとは言えないということである。

正しさの判定

では、どう正しさを判定するのかが必要である。

1.答えが正しいこと
=>完成するまでお皿に盛られない。といえるだろう。つまり、レシピ通りに進めていくなかで、必ず完成品がお皿に盛られれば正しいことがわかる。そして、完成品でないものが盛られれば、それはバグであるといえる。

2.必ず終わる
=>この判定はとても難しい。なぜなら、答えが定まるかどうかがわからないからである。つまり、上記のお母さんが作り出した肉じゃがは、三年と一か月でカレーができたならば、それは正しいアルゴリズムとは言えない。

1の判定は、何度も作るということで正しさが判定できるが、2の判定はどうだろうか。ここで注目すべきことは手順を進めていく中での『計算量』に注目してみよう。

つまり、レシピが三年かかる場合手順が多いことが考えられる。例えば、ニンジンを栽培するところから始めるかもしれないし、牛を飼育するところから始めるかもしれない。これでは、当然、手順は増えるに決まっている。

では、どう判定するのか。

正解は一つではない。

「肉じゃが　レシピ」と検索すれば無数のレシピが出てくる。そこには様々なレシピがある。つまり、「問題」を解決する「手順」は一つではないのである。

であるならば、どのレシピが手順がもっともはやく作れるか(手順がすくない)を判定すればよいことになる。

以上から、アルゴリズムの正しさの判定は、1.答えが正しいこと。2.様々なアルゴリズムのなかでもっとも計算量が少ないこと。からアルゴリズムの正しさを判定することができるわけである。

計算量の判定

アルゴリズムの正しさには2つの判定があると説明してきた。ただ、2つ目の計算量での判定には、計算量のまえに問題の規模に注目する必要がある。以下が線形探索と2分探索の例である。

線形探索はいわば、一つずつ見ていくということである。

func main() {
	var a []int //任意に与えられた、数字の配列
	var x int //目標となる探索する数字
	fmt.Scanf("%d", &a)
	fmt.Scanf("%s", &x)

	isFound := false //配列の中に、探索する数字があるかの真偽値

    //ループで一つずつ探索
	for i := range a {
		if x == i {
			isFound = true
		}
	}

	fmt.Println(isFound)
}

for文で配列を、ループさせてif文で条件分岐させるコードである。つまり、配列内の数字を取り出して、xと同じか見るということである。

a=[1,2,3]、x=2のとき
aから、一つ目の1を取り出してxと同じかを判定する。
当然、違うので
aから、二つ目の2を取り出して、同じことを繰り返す。

というコードになる。

次に、二分探索は以下のようなコードになる。

func main() {
	var a []int //任意に与えられた、数字の配列
	var x int   //目標となる探索する数字
	fmt.Scanf("%d", &a)
	fmt.Scanf("%s", &x)

	isFound := false //配列の中に、探索する数字があるかの真偽値

	// 配列をソート（2分探索に必要）
	sort.Ints(a)

	isFound = binarySearch(a, x)

	fmt.Println(isFound)
}

func binarySearch(arr []int, target int) bool {
	left, right := 0, len(arr)-1

	for left <= right {
		mid := left + (right-left)/2 // 中央のインデックスを計算
		if arr[mid] == target {
			return true // 見つかった場合
		} else if arr[mid] < target {
			left = mid + 1 // 右半分に絞る
		} else {
			right = mid - 1 // 左半分に絞る
		}
	}

	return false // 見つからなかった場合
}

二分探索は、まず配列に細工をする(ソート）つまり、『小さい順にする』という操作をする。sort.Ints(a)の部分である。
次に、名前の通り小さいほうと大きいほうに二分する。そして、真ん中の値をxと比較して、xが真ん中の値よりも大きければ、探索すべきは、大きい方になる。それをまた、二分して.…、を繰り返していくうちに、値を探索するという方法である。

a=[5,1,3,2,4]、x=4のとき

1.aをソートする。
=>[1,2,3,4,5]
2.aを二分にする。
=>la=[1,2,3]と、ha=[4,5]
3.真ん中は3であるから、3より4のが大きいので、haの中から探索をする。
4.haを二分するし、1.へ

というコードになる。

計算量は、以下のようにあらわせる。
線形探索は、O(n)「オーダーｎ」となる。二分探索は、O(log n)となる。
(ｎ=配列の長さ）

n が増えた場合

  1. 線形探索 (O(n))
    配列が長くなるほど、探索回数が直線的に増加します。例えば、

    • n=10 → 最大 10回の比較

    • n=100 → 最大 100回の比較

    • n=1,000,000 → 最大 1,000,000回の比較

  2. 二分探索 (O(log n))
    配列が長くなっても、探索回数は緩やかに増えます。例えば、

    • n=10 → 最大 ⌈log⁡2(10)⌉=4 よって、4 回の比較

    • n=100 → 最大 ⌈log⁡2(100)⌉=7 よって、7 回の比較

    • n=1,000,000 → 最大 ⌈log⁡2(1,000,000)⌉=20 よって、20 回の比較

となる。つまり、二分探索の方がｎを増やせば増やすほどに計算量が少なくなる。ということは、二分探索の方が線形探索より"正しい"といえる。

ただ、nを見る必要がある。つまり、二分探索はコードを見ればわかる通り複雑である。であるから、nがそこまで大きくないときには、むしろ線形探索の方が"正しい"ときもあるだろう。

最後に

つまり、真実だけが一つなのだろうか。

noteっぽい？

いいなと思ったら応援しよう！