小编Mik*_*e V的帖子

我有一个计数算法,我试图得到一个大致的描述.它是可怕的嵌套和可怕的指数.这里是:

 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)/ 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 …