递归算法的时间复杂度

Question

每当我看到一个递归解决方案，或者我为一个问题编写递归代码时，很难弄清时间复杂度，在大多数情况下，我只是说它是指数级的？它实际上是如何指数级的？人们怎么会说它是2^n，当它是n!，当它是n^n或n^k时。

我有一些问题：

1.假设查找字符串的所有排列（O（n！））。 2.在数组中查找总和为k的所有序列（指数级别，我该如何精确计算）。 3.查找所有大小为k且总和为0的子集（k是否会出现在复杂性中，应该会出现吧）。

有人能帮我计算这些问题的精确复杂度吗？我能够为它们编写代码，但很难理解确切的时间复杂度。

- Peter

---

这是我在大学数学课程中的一个主题。我可以指出有关该主题的网页文章，例如http://en.wikipedia.org/wiki/Big_O_notation，但我怀疑您的问题（我认为是“如何计算任意算法的时间复杂度？”）的一般答案/解释可能太长/复杂，无法在此论坛上发布答案。因此，我将投票关闭此问题。 - ChrisW

@ChrisW，您能否举一个找到大小为k的子集并使其总和为0的例子，并讨论一下其复杂度。这将对我很有帮助。让我们讨论一下它的代码和时间复杂度（TC），代码很简单，但我该如何计算时间复杂度呢？ - Peter

此外，这种类型的问题之前也在这里讨论过，但并非针对困难的递归算法。 - Peter

你曾经尝试过编写递归关系来描述算法吗？一旦这样做，那么你就可以通过猜测和替换或者主定理来解决它。有些问题仍然很困难，但它涵盖了许多情况。 - goat

@Peter 对于这个问题，一个包含n个元素的集合有2^n个子集。对于所有这些子集计算总和，并进行比较。上限为n2^n。要获得2^n的界限，需要进行更仔细的分析。有两种类型的子集，一种包括最后一个元素，另一种不包括。找到所有子集的子集，它们的总和为K，并且总和为K-S(n)。这两个子问题都需要T(n-1)的时间，因此T(n)=2T(n-1)。 - Daniel Fischer

Answer 1

在一个数组中找到所有加起来等于k的序列（指数级别，如何精确计算）。

令 F(a, n, k) 为集合 S ⊂ {0, 1, ..., n-1} 的所有子集的数量，使得：

 ∑ a[i] == k
i∈S

我们可以通过将问题分成两个子问题（对于n>0）来递归计算F（array，array的长度，k）。

{0,1，...，n-1} 的子集可以分为包含n-1和不包含n-1的两类。

我们得到递归公式：

F(a,n,k) = F(a,n-1,k) + F(a,n-1, k-a[n-1])

让T(n)表示计算F(_,n,_)所需的时间（下划线表示T(n)仅取决于n，而不是数组或k [尽管对于特定的数组和k，可以使用更快的算法]）。然后，F的递归立即暗示了：

T(n) = 2 * T(n-1)

n > 0。

当n == 0时，我们可以在常数时间内计算出解决方案。

F(a, 0, k) = k == 0 ? 1 : 0

所以我们用归纳法得到 T(n) = 2^n * T(0)。

如果不仅要计算子集，还要输出它们，那么时间复杂度为 O(n * 2^n)，这是最紧的上界（对于一个全是0的数组，当且仅当k == 0时，所有子集都符合条件，并且打印它们需要Θ(n * 2^n)时间）。

找出所有大小为 k 的子集，使它们的和为 0（k是否会在复杂性中出现？应该出现吧？）。

是的，该问题的复杂度取决于 n 和 k。

设 F(a,n,k,s) 是元素集合 {0, 1, ..., n-1} 中所有大小为 k，满足以下条件的子集S的数量：

 ∑ a[i] == s
i∈S

对于 k == 0，我们再次有一个常数时间的答案，如果 s == 0，则存在一种这样的子集（空集），否则不存在。 对于 k > n，集合 {0, 1, ..., n-1} 没有基数为 k 的子集，因此如果 k > n，则 F(a,n,k,s) = 0。

如果 0 < k <= n，我们可以像上面一样，分别考虑包含 n-1 和不包含 n-1 的子集，给出

F(a,n,k,s) = F(a,n-1,k,s) + F(a,n-1,k-1,s - a[n-1])

而对于时间复杂度，我们发现

T(n,k) = T(n-1,k) + T(n-1,k-1)

递归在二项式系数中是众所周知的，我们有

T(n,k) = n `choose` k = n! / (k! * (n-k)!)

(其中 T(n,0) = 1）。

再次强调，如果不仅要计算集合数量，还要输出所有集合，则时间复杂度会增加。在这里，所有集合的基数都为 k，因此复杂度变为

k * n! / (k! * (n-k)!)

- Daniel Fischer

Answer 2

看一下主定理。它在斯坦福大学的Tim Roughgarden教授的算法：设计与分析：第一部分中得到了完美的解释。这些都是在线课程，我推荐你去上，但你也可以在不注册课程的情况下观看视频。如果你感兴趣，还有第二部分的课程。

- Adam Stelmaszczyk

---

我知道主定理，如果给出递归式，我可以解决它。但是对于一些问题编写递归式是我发现困难的 :( 你能否选择其中一个问题并帮助我编写递归式？当我编写和计算时，我发现它是n^n，但有人说它是2^m，我真的很困惑。 - Peter

你所讲的课仅解释了那些标准的基本算法，例如归并排序、二分查找等。我需要帮助解决那些难以判断复杂度的非基本问题。我不想简单地说它是指数级别的，我想知道它具体是多少以及为什么会这样。 - Peter

主定理适用于一组有限的递归问题，即那些出现在传统分治算法中的问题。它并非推导渐进复杂度的万能工具。 - Fred Foo