低效的分治算法的复杂度

Question

一个大小为n的实例被分成p≥2个大小为n-a的实例，其中a是一个小的整数，p是一个常数。这个操作（即分割为多个实例）的计算成本为1个单位，其中C(0)=1。

我试图找出这种设计的复杂度。我在将这些词语转换为等式方面遇到了困难，以下是我认为递归应该看起来像的内容：

C(n) = (n-a)*C(n/p) + 1

这句话用中文怎么说？

- Jacek Trociński

---

不，它不是这样的。请再仔细阅读一遍问题，并确定创建的子问题数量以及每个子问题的大小。目前，方程式中这些都是错误的。 - naitoon

记住公式是：C（规模）=（子问题数量）* C（子问题规模）+（分割成本）。你已经知道了所有的东西，只要正确地解释这个公式就可以了。我不会直接回答这个问题，我希望你能够自己解决。 - naitoon

还要知道，如果没有人回答，而你确实找到了答案，你可以回答自己的问题。如果你这样做，请确保在回答中提供一个充分的解释。 - BlackVegetable

我正在对这个问题进行负评，因为我认为SO不是一个作业帮助的地方。它对SO档案库没有任何有用的贡献：没有人会搜索“低效的分治算法”，而且这个例子过于简单和人工，对于工作中的程序员来说没有任何帮助。同时，这也浪费了其他人的时间，而你并没有像本应该学到的那么多。（我知道我们都有自己特殊的情况，有时非常困难，但这仍然是我的观点。） - Sergey Orshanskiy

@SergeyOrshanskiy 这是两种情况之一，应避免使用分治算法...作为程序员，知道何时编写迭代或递归代码非常重要。 - Jacek Trociński

Answer 1

我认为它应该是这样的：

C(n) = (p)*C(n-a) + 1

我的理解是，您在问题中提到了“每个大小为n-a的实例的数量≥2”，因此大小缩减为C(n-a)，并且有p个子问题。所以我认为答案类似于p*C(n-a)。您已经正确得到了另一个项。每个步骤的分割成本为C(0) = 1，就像您所说的那样。

- Shashank

---

嗯...我现在也是这么想的，但这会不会是指数级复杂度呢...我会继续尝试的。 - Jacek Trociński

你在标题中提到了“低效”这个词。也许这正是这个问题的关键，展示了分治算法可以实现近乎指数时间复杂度的可能性。 - Shashank

Answer 2

好的，既然这看起来像是一项学校作业，特别是因为有“低效的分治算法”这样的措辞，我也不会直接回答它。

我的建议是以a=1和p=2为例。在这种情况下，您必须解决两个大小为n-1的子问题，然后花费1个单位的时间来组合解决方案。如果解决n=1需要1个单位的时间，即C(1)=1，那么您会得到

C(1)=1
C(2) = 2*C(1) + 1 = 3
C(3) = 2*C(2) + 1 = 7
C(4) = 2*C(3) + 1 = 15

等等，你得到了 C(n) =2^n - 1。如果 a 不是 1，那么基本上是一样的：你只需要将其提高到幂 n/a 而不是 n。

顺便说一下，你把 a 称为“小整数”，而 p 是“常数”，这不是很奇怪吗？当然，两个表达式意思是一样的。就渐近行为而言，所有常数都是“小”的。

- Sergey Orshanskiy

---

我同意措辞有些奇怪...最终我发现复杂度为C(n) = p^(n/a) + [(p^(n/a) - 1) / (p - 1)]，这将是指数级别的大O(p^n)。 - Jacek Trociński

Answer 3

正如Shashank所写的，C(n) = p⋅C(n-a) + 1是正确的。

我只想提一下，这会导致

C(n) = Σ_i=0,...,n/a pⁱ = p^{n/a + 1} - 1

因此，C(n)在O(p^n/a)中，这在n方面是指数级的。

- AbcAeffchen