algorithm - 低效分治算法的复杂性

Question

一个 size 的实例被n划分为p≥2size为 small和a的实例。该操作（即划分实例）的计算成本是一个单位，其中n-aaintegerpconstantC(0)=1.

我试图找出这种设计的复杂性。我无法将单词放入等式中，这是我认为递归应该是这样的：

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

这个对吗？

Answer 1

我认为它会是这样的：

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

我的理由是您在问题中说“p≥2 个实例，每个实例的大小为 na”。因此大小减小到C(n-a)并且有 p 个子问题。所以我认为它会是这样的p*C(n-a)。你说对了另一个术语。每一步划分的成本C(0) = 1如你所说。

Answer 2

As Shashank wrote C(n) = p⋅C(n-a) + 1 is correct.

I just want to mention that this results in

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

So C(n) is in O(p^n/a), which is exponential in n.

Answer 3

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

我的建议是使用a=1和p=2作为一个例子。在这种情况下，您必须解决两个 size 的子问题n-1，然后花费 1 个单位的时间来组合解决方案。如果你需要 1 个单位的时间来解决n=1ie 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为“常数”不是很奇怪吗？当然，这两个表达的意思是一样的。就渐近行为而言，所有常数都是“小”的。