计算分区功能

Question

在任何相对效率的已知算法中都存在，以计算分区函数 < Span Class=“Math-Container”> $ P（n）$ 给定 $ n $ ？这个问题的复杂性类别作为 $ n $ 的函数

也许我在这里缺少一些微不足道的东西，但除了列出这种功能的一些经常性定义和一些渐近学，我没有看到这种精确的信息（复杂性类，以及具有它们的运行时/空间复杂性的已知算法）在这些文章中的任何一个：

• 分区（数字理论）
• 分区功能（数字理论）

Answer 1

Johansson在他的论文中提供了几乎线性的时间算法（在输出大小方面！）。在 wikipedia文章