1
правка
Изменения
м
→Алгоритм за O(N3/2): Алгоритм за n^(3/2) не является самым быстрым, задача решается за nlogn
{{Задача
|definition =
По заданному числу <tex>n</tex> найти количество его различных разбиений на положительные слагаемые<ref name="amount" /> <tex> m_0 + m_1 + m_2 + \dots ldots + m_k = n </tex> так, что при всех <tex> i: \colon m_i \leqslant m_{i+1} </tex>.}}
__TOC__
<tex dpi = "145">P(n, m, k) =
\left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 < m \leqslant n, 0 < k \leqslant n \\
P(n, m, n), & k > n \\
1, & n = 0, m = 0 \\
0, & \text{otherwise} \end{array} \right.
разбиения, которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(n, m, k - 1)</tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, то есть <tex>P(n - k, m - 1, k)</tex>.
Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования]] с мемоизацией меморизацией будет иметь асимптотику <tex>O(n^{3})</tex>.
== Алгоритм за O(N<sup>2</sup>) ==
== Алгоритм за O(N<sup>3/2</sup>) ==
Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <tex> O(n \sqrt{n}) </tex>.
Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.
