Расчет сложности времени максимальной суммы подпоследовательности

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 раза (для внутреннего цикла) по n^2 раза (для двух наружных петли), в результате чего в общей сложности n^3.

Чтобы получить конкретную функцию (n^3 + 3n^2 + 2n)/6, вам нужно быть более тщательным в своих расчетах и ​​позаботиться обо всех тех факторах, которые я просто пропустил выше.

Answer 3

Проверить this solution предложил Марк Аллен Вайс (в своей книге).