简化这种指数算法的Big-O复杂性

Question

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

 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 * (n * e / k)^k * (2^n))

我的问题是,我在这里可以忽略什么... 2 ^ n肯定是主导术语,因为n总是大于k,通常更加如此.这可以简化为O(2 ^ n)吗？或者O(2 ^可怕)？或者我应该留在2 ^ k,如在O(2 ^ k*2 ^ n)？(或保留所有条款？)

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

Answer 1

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

是的,但另一种方式不是 - 意思是 - 当涉及到大O符号时,它是不可忽视的,即使它不与n竞争.它只能如果MAX_K是有界的一个常数被忽略(有一个常数c这样k <= c).例如 - O(n * logk)算法不是O(n),因为k因子不是有界的,因此对于每个常数都存在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 < n那时O(n + k) = O(n),因为有一个常数c,N对所有人来说n > N:c*n < n + k,但在处理产品时当然不是这样.