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>.
<ref name="young">[http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.94.D0.B8.D0.B0.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D1.8B_.D0.AE.D0.BD.D0.B3.D0.B0 Википедия {{---}} Диаграммы Юнга]</ref>
</references>
==См. также==
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Производящая функция]]
== Источники информации ==
