54
правки
Изменения
м
→Разбиение на слагаемые: dp исправлено на d, ... исправлены на \ldots, добавлено пояснение асимптотики
*<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении.
*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.
*<tex>\mathtt{part[1..\ldots N]}</tex> {{---}} данное разбиение
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.
<p>
<tex dpi = "145">d[i][j] =
\left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j \\ d[i][j + 1] + dpd[i - j][j], & i > j \end{array} \right.
</tex>
</p>
last = part[i] <font color=green>// обновляем последний поставленный элемент </font>
'''return''' numOfPart <font color=green>// возвращаем ответ</font>
Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>
Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.
