c++ - 最大サブシーケンス合計の時間計算量の計算

Question

みなさん、こんにちは。Maximum Subsequence Sum の時間計算量を計算しようとしています。実際、私は O(n^3) である答えを知っており、関数 (n^3 + 3n^2 + 2n)/6 から得られます。

私の質問は、その機能がどのように得られるかです。

Answer 1

実際には、コード内のループを見てください。

for (int i=0; i<n; i++)
    for(j = i; j<n; j++) {
        ...
        for (int k=i; k<=j; k++)
            XXX;

外側のループは明らかに から まで実行され、「中間」ループは( 、、 ...で始まる) から まで実行されるため、行XXXはn^3(一定の係数と の累乗を法とする) 回実行されます。内側のループは約回「開始」されます。ここで、との両方が依存する(たとえば、最初の外側の反復の最後にとになる) ため、 lineは(内側のループの場合)回 (外側の 2 つのループの場合) 倍になり、合計は.n0n-1i01n-1n^2ijni0j=n-1XXXnn^2n^3

具体的な関数を取得するに(n^3 + 3n^2 + 2n)/6は、計算をより綿密にし、上で省略したすべての要因を処理する必要があります。

Answer 2

これが方法です..

i=0
j=0 k=0              (count=1 )
j=1 k=0,1            (count =2)
j=2 k=0,1,2          (count = 3)
...
j=n-1 k=0,1,2,...n-1  (count = n)

Total number of times code executed = 1+2+3+...+n =  n(n+1)/2

i=1
j=1 k=1              (count=1 )
j=2 k=1,2            (count =2)
j=3 k=1,2, 3          (count = 3)
...
j=n-1 k=1,2,...n-1  (count = n-2)

Total number of times code executed = 1+2+3+...+n-1 =  (n-1)n/2

...

i=n-1
j=n-1 k=n-1     ( count = 1)
Total number of  of times code executed = 1 = 1(1+1)/2


 Now if we sum for all the values of i

 n(n+1)/2 + ((n-1)((n-1)+1)/2+.....+1(1+1)/2

 =∑ N(N+1)/2 =1/2∑(N^2 +N) =1/2(∑N^2+∑N)=1/2{  1/6  N(N+1)(2N+1) + 1/2 N(N+1) } =1/2{ (2N^3 + 3N^2+N )/6 +(N^2+N)/2} =(N^3 + 3N^2 + 2N)/6

Answer 3

Mark Allen Weiss (著書) が提案したこの解決策を確認してください。