Время выполнения решения для динамического программирования из предыдущего поста (шары в контейнеры)

Question

В вопросе Расчет количества шариков в ячейках по нескольким значениям с использованием динамического программирования В ответе обсуждается алгоритм динамического программирования для помещения шариков в ячейки, и я пытался определить время выполнения, как оно естьне учтены в ответе.

Краткое резюме: Учитывая M неразличимых шаров и N различимых ячеек, запись в таблице динамического программирования Entry [i] [j] представляет количество уникальных способов размещения i шаров. в j бункерах.

S[i][j] = sum(x = 0 -> i, S[i-x][j-1])

Очевидно, что размер двумерного массива динамического программирования равен O (MN). Однако я пытаюсь определить влияние суммирования на время выполнения.

Я знаю, что суммирование значений (1 .... x) означает, что мы должны получить доступ к значениям от 1 до x. Значит ли это, что для каждого вычисления записи, поскольку мы должны получить доступ не более чем к 1 ... M другим значениям, время выполнения находится в области O ((M ^ 2) N)? Буду признателен за любые разъяснения. Спасибо!

Answer 1

Вы можете избежать чрезмерного времени для суммирования, если сохраните суммы столбцов в дополнительной таблице.

Когда вы вычисляете S[i][j], также заполните Sums[i,j]=Sums[i-1,j] + S[i,j] и позже используйте это значение для ячейки справа S[i,j+1]

PS Обратите внимание, что вам действительно нужно хранить только две строки или даже одна строка таблицы сумм