计算最大子序列和的时间复杂度

Question

大家好，我试着计算最大子序列和的时间复杂度。实际上，我知道的答案是O (n^3 )，它是从函数(n^3+ 3n^2 + 2n)/6得到的。

我的问题是这个函数是如何得到的。

​

Answer 1

这里是如何..。

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 2

很简单，实际上:看看代码中的循环。

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

行XXX被执行n^3时间(模一些常数因子和n的一些较低的幂)，因为外部循环显然从0运行到n-1，“中间”循环运行于i (从0，1，.)开始。对于n-1，意味着内部循环将“启动”大约n^2时间。现在，i和j都依赖于n (例如，在第一次外部迭代结束时，i将是0和j=n-1 )，因此，行XXX将是n^2时间(对于内部循环)乘以n^2时间(对于外两个循环)，从而导致总的n^3。

要获得具体的函数(n^3 + 3n^2 + 2n)/6，您必须在计算中更加彻底，并处理我前面忽略的所有因素。

Answer 3

请查看Mark建议的这个解决方案 (在他的书中)。