Как суммирование подмассива повлияет на сложность времени во вложенном цикле for?

Question

Пытаюсь вычислить временную сложность некоторого простого кода, но я не знаю, как вычислить временную сложность при суммировании подмассива.Код выглядит следующим образом:

for i=1 to n {
   for j = i+1 to n {
       s = sum(A[i...j])
       B[i,j]=s
}}

Итак, я знаю, что вложенные циклы неизбежно дают нам O (n ^ 2), и я считаю, что функция суммирования для подмассива также O (n ^ 2).).Тем не менее, я думаю, что временная сложность для всего алгоритма O (n ^ 3).Как мне сюда добраться с этой информацией?Спасибо!

Answer 1

Мне нравится думать о циклах как об суммировании.Таким образом, число шагов (записанных как функция, T(n)):

T(n) = \sum_{i=1}^n numStepsInInnerForLoop

Здесь я использую что-то, написанное в псевдо-MathJax, и записал внешний цикл for каксуммирование от i=1 до n количества шагов во внутреннем цикле for (один от i+1 до n).Вы можете думать об этом как о суммировании количества шагов во внутреннем цикле for от i=1 до n.Подстановка в numStepsInInnerForLoop приводит к:

T(n) = \sum_{i=1}^n [\sum_{j=i+1}^n numStepsOfSumFunction]

Эта функция теперь представляет число шагов, в которых оба цикла были выделены в виде суммирования.Предполагая, что s = sum(A[i...j]) делает j-i+1 шагов, а B[i,j]=s делает только один шаг, мы можем заменить numStepsOfSumFunction этими более полезными параметрами, и теперь уравнение становится:

T(n) = \sum_{i=1}^n [\sum_{j=i+1}^n (j-i+1 + 1)]

Когда вы решите эти суммирования(используя вид формул, которые вы видите на на этой странице учебника по суммированию ), вы получите кубическую функцию для T(n), которая соответствует O(n^3).

Answer 2

Ваши рассуждения заставляют меня поверить, что вы используете этот алгоритм для массива размера n.Если это так, то каждый раз, когда вы вызываете метод sum во внутреннем цикле for, вы вызываете этот метод для определенного диапазона значений (индексы от i до j).Для каждой итерации цикла for этот метод sum будет проходить через 1, 2, 3, ..., а затем, наконец, n элементов в последней итерации при увеличении j от (i + 1) до n.Обратите внимание, что это когда i = 1. При увеличении i он больше не обязательно будет переходить от 1, 2, 3, ..., n к n, поскольку технически он будет увеличиваться до n - i элементов.Большая О, однако, является наихудшим случаем, поэтому мы должны использовать этот сценарий.

1 + 2 + 3 + ... + n дает нам n ^ 2.Время выполнения метода sum зависит от значений i и j;однако при запуске в цикле for с заданными условиями общая сложность времени всех вызовов sum в одной итерации внутреннего цикла for составляет O (n ^ 2).И наконец, поскольку этот внутренний цикл for выполняется n раз, общая сложность времени для всего алгоритма составляет O (n ^ 3).