我有一个计数算法,我想得到一个通用的大O描述。它非常嵌套和指数级复杂。以下是该算法:
这里是每个运行时间的逐行解释:
众所周知,(n个数中选k个数)的结果不会超过(n * e / k)^k,因此:
我的问题是,我应该忽略什么...因为n总是大于k,而且通常要大得多,所以2^n肯定是占主导地位的。这是否可以简化为O(2^n)?或者O(2^terrible)?或者应该保留2^k,比如O(2^k * 2^n)?(或者保留所有项?)
我的理解是,如果k或max_k可以与n竞争或超过n,则它们是至关重要的。但是由于它们总是被支配,所以它们可以像多项式运行时间的低阶项一样被丢弃吗?我认为所有指数运行时间的混乱使我感到困惑。任何建议都将不胜感激。
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.
这里是每个运行时间的逐行解释:
- 这是一个简单的划分,我将给它一个常数c1。
- max_k是一个很小的数字,始终小于n,可能在4或5左右。我会在下面使用k。
- 这个循环总共运行2^k*(n choose k)次
- 通过将第1行视为常数,我们可以推广这一行,并知道它在最坏情况下总共不会超过2^n次,但通常只运行2^n的一部分,因此我们将其称为(2^n)/c2.
- 这是所有这些循环中的简单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,则它们是至关重要的。但是由于它们总是被支配,所以它们可以像多项式运行时间的低阶项一样被丢弃吗?我认为所有指数运行时间的混乱使我感到困惑。任何建议都将不胜感激。
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