我有一个计数算法,正试图对此进行通用的big-o描述。它是可怕的嵌套和可怕的指数。这里是:
I have a counting algorithm for which I am trying to get a general big-o description. It is horribly nested and horribly exponential. Here it is:
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.此处是每次运行时间的逐行提示
Here is a line-by-line idea of each running time
将所有这些相乘得到:
c1 * k * 2^k * (n choose k) * (2^n)/c2 * c3由于我要使用big-O表示形式,因此忽略常量:
Since I want a big-O representation, ignoring constants gives:
k * 2^k * (n choose k) * (2^n)它是kn拥有(n选择k)的上方是(n * e / k)^ k的边界,因此:
It is known that (n choose k) is bounded above by (n * e / k)^k, so:
O(k * 2^k * (n * e / k)^k * (2^n))我的问题是,在这里我可以忽略什么... 2 ^ n当然是主要项,因为n总是大于k,通常更大。可以简化为O(2 ^ n)吗?还是O(2 ^可怕)?还是应该像O(2 ^ k * 2 ^ n)一样留在2 ^ k中? (或者保留所有术语?)
My question is, what can I ignore here... 2^n is certainly the dominating term since n is always larger than k, and typically much more so. Can this be simplified to O(2^n)? Or O(2^terrible)? Or should I leave in the 2^k, as in O(2^k * 2^n)? (or leave all the terms in?)
我的理解是,如果k或max_k可以竞争或超过n,那么它们至关重要。但是,由于它们始终处于支配地位,是否可以像多项式运行时间的低阶项一样将其丢弃?我想所有的指数运行时间混乱使我感到困惑。
My understanding is that if k or max_k can compete or surpass n, then they are vital. But since they are always dominated, can they be discarded like lower order terms of polynomial running times? I suppose all the exponential running time mess is confusing me. Any advice is greatly appreciated.
推荐答案
我的理解是,如果k或max_k可以竞争或超越n,然后是至关重要的
My understanding is that if k or max_k can compete or surpass n, then they are vital
是的,但是相反-不是-不能忽略当涉及到大O表示法时,即使它不与n竞争。 仅当max_k以常量为边界时,才可以忽略(存在常量 c 使得 k< = c )。例如- O(n * logk)算法不是 O(n)算法,因为k因子不是有界,因此存在 k ,使得 nlogk>每个常量 c c * n 。
True, but the other way around isn't - meaning - it cannot be ignored when it comes to big O notation, even if it does not compete with n. It can be ignored only if max_k is bounded with a constant (there is a constant c such that k <= c). For example - O(n * logk) algorithms, are not O(n), since the k factor is not bounded and thus there exists a k such that nlogk > c*n for every constant c.
由于得到的表达式是a产品,您可以忽略的都是常量,在您的情况下-仅 e 让您 O(k * 2 ^ k *(n / k )^ k * 2 ^ n)。
Since the expression you got is a product, all you can ignore are constants, which in your case - is only e getting you 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)一个。
If k is bounded, then you can remove it from the expression as well in big O notation, and you will get O(n^k* 2^n). Note that even in this case, although n^k << 2^n, it still cannot be ignored, because for every constant c there exists some n such that c*2^n < n^k *2^n, so the algorithm is not a O(2^n) one.
在加法时可以忽略较小的因素。如果 k < n ,然后 O(n + k)= O(n),因为存在常量 c,N ,这样对于所有 n> N : c * n< n + k ,但是在处理产品时当然不是这样。
Smaller factors can be ignored when it comes to addition. If k < n then O(n + k) = O(n), because there is a constants c,N such that for all n > N: c*n < n + k, but this is of course not true when dealing with product.
更多推荐
简化此指数算法的Big
发布评论