『珠玉のプログラミング』 の中で、ある問題をアルゴリズムをリファクタしながら計算量オーダーを下げていく章がおもしろかったので、検証がてらgolangで書き直してみます。
問題
ある長さnの配列xには整数がランダムに入っています。
[2, 6, -37, 78, -1, 0, 87, 21, 3, -60]
例えば上の配列に対して、配列内の連続した任意の区間の要素の和を計算したとき、その値が最大になる区間はなんになるでしょうか。
上の配列に対しての解は、インデックス3から8の間の要素の和(78 + -1 + 0 + 87 + 21 + 3 = 188)で、どの部分和と比較してもこれが最大になります。
なお、計算においては0要素の和を認めます。もし配列の全体が負数だった場合、その解は0になるとします(まったく要素を選ばないため)。
O(n^3)の解
まずは素朴に総当りで考えていきます。開始インデックスiを0<=i<nの範囲、終了インデックスを0<=j<nの区間で走査します。そしてそれぞれの区間に対して、和を計算します。コードの例は以下になります
package main
import "fmt"
func main() {
array := []int{2, 6, -37, 78, -1, 0, 87, 21, 3, -60}
ans := solve(array)
fmt.Println("answer is ", ans)
}
func sumArray(start int, end int, array []int) int {
sumValue := 0
for i := start; i <= end; i++ {
sumValue += array[i]
}
return sumValue
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func solve(array []int) int {
maxSumValue := 0
n := len(array)
for i := 0; i < n; i++ { // (i
for j := 0; j < n; j++ { // (ii
sumValue := sumArray(i, j, array) // (iii
maxSumValue = max(sumValue, maxSumValue)
fmt.Println(i, j, maxSumValue, sumValue)
}
}
return maxSumValue
}
(i、 (iiの箇所で二重ループになることと、(iiiの部分がO(n)相当の処理なため、n * n * nでO(n ^ 3)の計算量となります。
O(n)の解
実はこの解を導く時、O(n)のオーダーまで計算量を落とすことができます。
例えば次のような配列について考えます。
[-1, 2, 6, -37, 78, ...]
この配列がもし、
[-1, 2, 6]
だったら、解は2 + 6 = 8です。
次に、
[-1, 2, 6, -37]
だったら、-37まで足してしまうと8より小さくなってしまうので、これも解は今までの最大値8です。
ここで、
[-1, 2, 6, -37, 78]
の場合、今までの最大値8と一番右の値78を含んだ場合の最大値2 + 6 -37 + 78 = 49を比較して、解は49となります。
つまり、インデックスをひとつずつずらしていって、その度に、今までの最大値と一番右の値を含んだ場合の最大値を比較することによって、解を得ることができます。
これをコードに表すと、
package main
import "fmt"
func main() {
array := []int{2, 6, -37, 78, -1, 0, 87, 21, 3, -60}
ans := solve(array)
fmt.Println("answer is ", ans)
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func solve(array []int) int {
pastMaxSumValue := 0
currentAggValue := 0
n := len(array)
for i := 0; i < n; i++ {
currentAggValue = max(currentAggValue+array[i], 0)
pastMaxSumValue = max(pastMaxSumValue, currentAggValue)
fmt.Println(pastMaxSumValue, currentAggValue, array[i])
}
return pastMaxSumValue
}
というようになります。
ここで、一番右の値を含んだ場合の最大値currentAggValueは、左端からの部分和をとりながら、0より小さい場合は0で値を更新することによって計算しています。
（この計算中、currentAggValueはpastMaxSumValueの影響を受けないところが注意点です）
このアルゴリズムでは、和を取りながら一回だけ配列を走査しているため、計算量はO(n)となります。
速度計測
しかし、本当に後者のアルゴリズムはO(n)なのでしょうか？ また、O(n)だとどのくらいO(n^3)と計算速度が異なるのでしょうか？
それではO(n^3)アルゴリズムとO(n)アルゴリズムを、nを増やしながらそれぞれ1000回計測してみます。
計測は、
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
test()
}
func test() {
count := 1000
length := 10
var array [10]int
for i := 0; i < length; i++ {
array[i] = rand.Intn(length) - length/2
}
fmt.Println(array)
start := time.Now()
for i := 0; i < count; i++ {
solve(array[:])
}
end := time.Now()
fmt.Println((end.Sub(start)).Seconds(), " second")
}
のように行いました。そして結果は以下のとおりです。
| n | O(n^3) | O(n)[s] |
|---|---|---|
| 10 | 0.00087 | 0.00002 |
| 100 | 0.18701 | 0.00012 |
| 1000 | 121.42791 | 0.00150 |
(n=10000の場合を計算するのは躊躇してしまいました。。。)
O(n^3)の時間の増え方がO(n)に比べてはるかに早いことが見て取れます。
このように、素朴に考えるとO(n^3)かかってしまう計算が、アルゴリズムの工夫（いわゆるしゃくとり法に考え方は近いと思います）によってO(n)までオーダーを下げられることがわかりました。
『珠玉のプログラミング』では他にもこの問題に対する複数の解が掲載されているので、気になる方はぜひ読んでみてください。