golangで計算量オーダーを実感する


[『珠玉のプログラミング』](https://www.amazon.co.jp/%E7%8F%A0%E7%8E%89%E3%81%AE%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-%E6%9C%AC%E8%B3%AA%E3%82%92%E8%A6%8B%E6%8A%9C%E3%81%84%E3%81%9F%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BB%E3%83%99%E3%83%B3%E3%83%88%E3%83%AA%E3%83%BC/dp/4621066072) の中で、ある問題をアルゴリズムをリファクタしながら計算量オーダーを下げていく章がおもしろかったので、検証がてら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の区間で走査します。そしてそれぞれの区間に対して、和を計算します。コードの例は以下になります

```golang
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となります。

つまり、インデックスをひとつずつずらしていって、その度に、`今までの最大値`と`一番右の値を含んだ場合の最大値`を比較することによって、解を得ることができます。

これをコードに表すと、

```golang
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回計測してみます。

計測は、

```golang
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)までオーダーを下げられることがわかりました。

『珠玉のプログラミング』では他にもこの問題に対する複数の解が掲載されているので、気になる方はぜひ読んでみてください。