Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

『珠玉のプログラミング』 の中で、ある問題をアルゴリズムをリファクタしながら計算量オーダーを下げていく章がおもしろかったので、検証がてら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)までオーダーを下げられることがわかりました。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away