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

Question

一个大小为n的实例被分成p≥2个实例，每个实例大小为n-a，其中a是一个小的 integer 而 p 是一个 constant。此操作(即划分实例)的计算成本是一个单位，C(0)=1。

我试图找到这个设计的复杂性。我无法将这些词放入等式中，我认为递归应该如下所示:

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

这是正确的吗？

Answer 1

我想应该是这样的:

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

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