简化这个指数算法的Big-O复杂度

Question

我有一个计数算法，我想得到一个通用的大O描述。它非常嵌套和指数级复杂。以下是该算法：

 1. For each T_i in T
 2. For k = 1 to max_k
 3. For each of 2^k*(n choose k) items
 4. For each t in T_i
 5. check if the item is in t...etc.

这里是每个运行时间的逐行解释:

1. 这是一个简单的划分，我将给它一个常数c1。
2. max_k是一个很小的数字，始终小于n，可能在4或5左右。我会在下面使用k。
3. 这个循环总共运行2^k*(n choose k)次
4. 通过将第1行视为常数，我们可以推广这一行，并知道它在最坏情况下总共不会超过2^n次，但通常只运行2^n的一部分，因此我们将其称为(2^n)/c2.
5. 这是所有这些循环中的简单if语句操作，所以是c3。

将所有这些乘在一起得到:

c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3

我想要一个大O表示法，忽略常数得到：

k * 2^k * (n choose k) * (2^n)

众所周知，(n个数中选k个数)的结果不会超过(n * e / k)^k，因此：

O(k * 2^k * (n * e / k)^k * (2^n))

我的问题是，我应该忽略什么...因为n总是大于k，而且通常要大得多，所以2^n肯定是占主导地位的。这是否可以简化为O（2^n）？或者O（2^terrible）？或者应该保留2^k，比如O（2^k * 2^n）？（或者保留所有项？）

我的理解是，如果k或max_k可以与n竞争或超过n，则它们是至关重要的。但是由于它们总是被支配，所以它们可以像多项式运行时间的低阶项一样被丢弃吗？我认为所有指数运行时间的混乱使我感到困惑。任何建议都将不胜感激。

- Mike V

Answer 1

我的理解是，如果 k 或 max_k 能够与 n 竞争或超越 n，那么它们就是至关重要的。

没错，但反过来不行——也就是说，在大 O 符号表示法中，即使它与 n 没有竞争，也不能忽视它。只有当 max_k 受到一个常数的限制时才能忽略它（存在一个常数 c，使得 k <= c）。例如，O(n*logk)算法并非O(n)，因为 k 因素没有被限制，因此存在一个 k，使得 nlogk > cn，对于每个常数 c。

由于你得到的表达式是一个乘积，你只能忽略常数，而在你的情况下，只有 e，从而得到了O(k*2^k * (n/k)^k * 2^n)。

如果 k 是有限的，则在 O 符号表示法中也可以从表达式中删除它，然后你将得到 O(n^k*2^n)。请注意，即使在这种情况下，尽管 n^k <<< 2^n，但仍然不能被忽略，因为对于每个常数 c，都存在一些 n，使得 c*2^n < n^k *2^n，因此该算法不是O(2^n)算法。

当涉及加法时，较小的因子可以被忽略。如果 kN：c*n < n+k，但处理乘积时当然不是这样。

- amit

---

如果n始终大于k，那么这是否足以限制k并将其移除？我想这就是你所说的，但我想确认一下。你提供的n*lg(k)示例非常清晰--谢谢你。 - Mike V

@Chucktown: “如果n始终大于k，那么这是否足以限制k并因此将其删除？” 不是的。当我们说“k被限制”时，我们的意思是存在一个常数“c”，使得“k < c”。我会编辑以澄清这一点。 - amit

@amit：非常好 - 谢谢您的澄清。因此，既然我是这个算法的发明者，如果我声明k永远不会大于20，那么我现在有了我的c，从而通过一个常数来限制k，而不是n，从而得到更简单的运行时间。你同意吗？ - Mike V

@Chucktown: 是的。如果你知道 k 肯定小于20（或任何其他常数），那么你可以得到：k*2^k * (n/k)^k * 2^n <= 20 * 2^20 * (n/20)^20 * 2^n，这在 O(n^20 * 2^n) 的时间复杂度内。请注意，唯一不会被忽略的 k 在指数中 - 因为它影响 (n/k)^k。 - amit

@amit：你的答案非常棒。感谢你在这里的贡献，根据你的声誉分数，在其他无数地方也是如此。 - Mike V