简化此指数算法的Big-O复杂度 [英] Simplifying the Big-O Complexity of this Exponential Algorithm

问题描述

我有一个计数算法，正试图对此进行通用的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

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。

1. This is a simple partitioning and I'm going to just give it a constant c1.
2. max_k is a small number, always less than n, perhaps around 4 or 5. I will use k below.
3. This loop always runs 2^k*(n choose k) times
4. By considering line 1 constant, we can generalize this line and know it will never fire more than 2^n times in total in worst case, but generally will run a fraction of 2^n times, so we will call this one (2^n)/c2
5. This is the simple if-statement operation inside all these loops, so c3.

将所有这些相乘得到：

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-O复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！