55424


[Maximum Sum Sublist](https://www.geeksforgeeks.org/python-maximum-sum-
sublist/)という  
配列で複数の整数が与えられた時に、和が最も大きくなる範囲とその和を求める  
プログラミング問題があります。

この問題は時間計算量O(n^2)とO(n^3)で解くアルゴリズムがあるのですが  
同じアルゴリズムでも解釈によってO(n^2)にもO(n^3)にもなるとのことで  
明確にO(n^2)とO(n^3)と区別できるプログラムもしくはアルゴリズムをそれぞれ探しています。

以下のコードは時間計算量O(n^2)と考えていますが、A[i:j+1]がO(j −
i)回かかるので、O(n^3)と[他の回答](https://stackoverflow.com/questions/56374508/is-there-
any-algorithm-whose-time-complexity-is-on3-for-maximum-sum-
sublist?noredirect=1)で説明されました。

[code]

    def solution(A):
        start = None
        end = None
        max_total = 0
    
        for i in range(len(A)):
            for j in range(i, len(A)):
                tmp = sum(A[i:j+1])
                if max_total < tmp:
                    max_total = tmp
                    start = i
                    end = j
    
        return max_total, start, end
    
    
    if __name__ == '__main__':
        A = [18, -10, 30, 23, -26]
        ans = solution(A)
        print(ans)
    
[/code]

Maximum Sum Sublistを解く時に  
明確にO(n^2)とO(n^3)と区別できるプログラムもしくはアルゴリズムが知りたいです。


CC BY-SA 4.0
2019-06-01T02:55:59.627
55421
2019-06-01T16:33:48.197
question
python アルゴリズム
Maximum Sum Sublistというプログラミング問題をO(n^2)とO(n^3)で解くアルゴリズムのちがいについて


コメントに書かせていただきましたが、ご質問中のコードは解釈の余地も何もなく明確に`O(n^3)`なので、あなたが見つけなければいけないのは、明確に`O(n^2)`のコード、と言うことになります。

(「`sum`の呼び出し回数」と言うことなら質問のコードは`O(n^2)`ですが、そんなものはアルゴリズムを議論する場合の計算量とは言いません。)

コメントの2個目のリンク中の質問側のコードを修正したものですが。これなら`O(n^2)`になります。

[code]

    def solution(A):
        start = None
        end = None
        max_total = 0
    
        for i in range(len(A)):
            tmp = 0
            for j in range(i, len(A)):
                tmp += A[j]
                if max_total < tmp:
                    max_total = tmp
                    start = i
                    end = j
    
        return max_total, start, end
    
    A = [18, -10, 30, 23, -26, 37, 48, -19, -13, 31]
    ans = solution(A)
    print(ans) #->(120, 0, 6)
    
[/code]

肝心なところは、`for
j`で回している内側ループ内には、`n`に応じて計算量が増えるような操作が入っていないことです。(計算量のことも考えずに「合計を求めるには`sum`を使わないとダサい」なんて短絡的な回答もあったようですが、ちゃんと1個ずつ足していかないと、`for
j`のループが`O(n)`になりません。)

ネット上を探せば`O(n * log n)`や`O(n)`の回答が見つかります。既にお気づきだろうとは思いますが。

* * *

# 【ざっくりと時間計算量の見積もり方】

まず大前提は、アルゴリズムを議論するときのBig-Oは、特に断らない限り時間計算量を表していると言うことです。

つまり、

## 基準量`n`の増減に対して、計算時間がどう増減するかを表す指標

であると言うことです。決して「見えている部分のループの回数」ではありません。

`n`を増やしていったら処理時間がどんどん増えていくのに、見かけのループがないから`O(1)`なんて指標を出されても困りますよね?

例えばこんな処理:

[code]

    for i in range(len(A)):
        A.sort()
        #... ソート結果を使う単純な処理
    
[/code]

があった場合に、`for i`での一重ループだから`O(n)`なんて結論を出したら、すぐにダメだしを食らうのはご理解いただけるでしょうか?

Pythonの`sort`の平均時間計算量は`O(n * log n)`ですから、それを`n`回繰り返すなら`O(n^2 * log
n)`と言うことになります。(もちろん`#...`の部分の計算量は`sort`の計算量に及ばない、と言うのが前提。)

* * *

と言うわけで、この回答のコードの時間計算量の見積もり。

[code]

                                         時間コスト
                                         --------
    def solution(A):
        start = None                     (この辺が全体コストに影響しないのは明白なんで無視)
        end = None
        max_total = 0
    
        for i in range(len(A)):          n^2 [=平均実行回数(n)*ループ1回分の実行コスト(n)]
            tmp = 0                        1
            for j in range(i, len(A)):     n [=平均実行回数(n/2)*ループ1回分の時間コスト(1)]
                tmp += A[j]                  1
                if max_total < tmp:          1 (trueでもfalseでも時間計算量は定数)
                    max_total = tmp            1
                    start = i                  1
                    end = j                    1
    
        return max_total, start, end
    
    
[/code]

Big-O記法の特性として、「定数倍は無視」「低次の項は無視」なんてことがあるので、`1+1`が`1`になったり、`n/2 *
1`が`n`になったりしています。

ご質問のコードの時間計算量の見積もりはこんな感じです。

[code]

                                         時間コスト
                                         --------
    def solution(A):
        start = None
        end = None
        max_total = 0
    
        for i in range(len(A)):          n^3 [=平均実行回数(n)*ループ1回分の時間コスト(n^2)]
            for j in range(i, len(A)):     n^2 [=平均実行回数(n/2)*ループ1回分の時間コスト(n)]
                tmp = sum(A[i:j+1])          n (`sum`関数の時間計算量は`O(n)`)
                if max_total < tmp:          1 (trueでもfalseでもは同上)
                    max_total = tmp            1
                    start = i                  1
                    end = j                    1
    
        return max_total, start, end
    
[/code]

この中で意識しておられなかったのは、「`sum`関数の時間計算量は`O(n)`」の辺りでしょうか。計算量が仕様に記載してあることの多い`sort`なんかに比べて「当たり前」の計算なんで、意識している人は少ないかも知れませんが、`sum`関数の実行には足し合わせる要素数`n`に比例した時間がかかります。

* * *

と言うわけで、

  * ループ内の処理が`O(1)`と考えられるプリミティブな処理ばかり⇒単純にループ回数＝時間計算量

  * ループ内に`O(1)`とは考えられない複雑な処理がある⇒そんなに単純に考えてはいけません

と言うことになります。

`sum`みたいな組み込み関数の実行にどの程度時間がかかるものなのかも、時間計算量を議論する時には忘れてはいけません。


CC BY-SA 4.0
2019-06-01T04:47:09.430
55424
2019-06-01T16:33:48.197
2019-06-01T16:33:48.197
13972
13972
55421
answer