6

我有一个计数算法，我正在尝试获得一个一般的 big-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 选择 k) 次
  4. 通过考虑第 1 行的常数，我们可以概括这条线，并且知道在最坏的情况下它总共不会触发超过 2^n 次，但通常会运行 2^n 次的一小部分，所以我们称之为 (2^n 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 choose k) 以 (n * e / k)^k 为界，所以：

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

我的问题是，我可以在这里忽略什么... 2^n 肯定是主要术语，因为 n 总是大于 k，而且通常更大。这可以简化为 O(2^n) 吗？还是 O(2^terrible)？还是我应该留在 2^k 中，如 O(2^k * 2^n)？（或保留所有条款？）

我的理解是，如果 k 或 max_k 可以竞争或超过 n，那么它们至关重要。但是由于它们总是被支配，它们可以像多项式运行时间的低阶项一样被丢弃吗？我想所有指数运行时间的混乱都让我感到困惑。任何意见是极大的赞赏。

4

1 回答 1

8

我的理解是，如果 k 或 max_k 可以竞争或超过 n，那么它们至关重要

是的，但反过来不是 - 意思是 - 当涉及到大 O 符号时，它不能被忽略，即使它不与 n 竞争。仅当 max_k 以常数为界时才可以忽略它（有一个常数c使得k <= c）。例如 -O(n * logk)算法不是，因为 k 因子是无界的，因此对于每个常量都O(n)存在一个k这样的。nlogk > c*nc

由于你得到的表达式是一个产品，你可以忽略的是常量，在你的情况下 - 只是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)一个。

当涉及到加法时，可以忽略较小的因素。如果k < nthen ，因为对于 all :O(n + k) = O(n)有一个常量，但是在处理产品时当然不是这样。c,Nn > Nc*n < n + k

于 2012-07-03T15:50:11.153 回答