找到你要的答案

Q:Big O for exponential complexity specific case

Q:指数复杂度的具体情况

Let's an algorithm to find all paths between two nodes in a directed, acyclic, non-weighted graph, that may contain more than one edge between the same two vertices. (this DAG is just an example, please I'm not discussing this case specifically, so disregard it's correctness though it's correct, I think).

We have two effecting factors which are:

  1. mc: max number of outgoing edges from a vertex.
  2. ml: length of the max length path measured by number of edges.

Using an iterative fashion to solve the problem, where complexity in the following stands for count of processing operations done.

for the first iteration the complexity = mc

for the second iteration the complexity = mc*mc

for the third iteration the complexity = mc*mc*mc

for the (max length path)th iteration the complexity = mc^ml

Total worst complexity is (mc + mc*mc + ... + mc^ml).

1- can we say it's O(mc^ml)?

2- Is this exponential complexity?, as I know, in exponential complexity, the variable only appear at the exponent, not at the base.

3- Are mc and ml both are variables in my algorithm comlexity?

让我们在一个有向无环的非加权图的两个节点之间找到所有路径,该算法可以在同一个顶点之间包含多个边。(这个图只是一个例子,请我不讨论这个案例具体,所以无视它的正确性,虽然它是正确的,我认为)。

我们有两个影响因素:

  1. mc: max number of outgoing edges from a vertex.
  2. ml: length of the max length path measured by number of edges.

使用迭代的方式来解决这个问题,其中的复杂性,在下面代表计数的处理操作完成。

对于第一次迭代的复杂性= MC

对于第二次迭代的复杂性= MC * MC

对于第三次迭代的复杂性= MC * MC * MC

对于(最大长度路径)第四次迭代的复杂度

最严重的复杂性是(MC + MC * MC +…克+毫升)。

1 -我们可以说它是O(MC -毫升)?

2 -这是指数复杂?我知道,在指数复杂度中,变量只出现在指数,而不是基。

3是MC和ML都是变量,在我的算法复杂度?

answer1: 回答1:

There's a faster way to achieve the answer in O(V + E), but seems like your question is about calculating complexity, not about optimizing algorithm.

Yes, seems like it's O(mc^ml)
Yes, they bot can be variables in your algorithm complexity

As about the complexity of your algorithm: let's do some transformation, using the fact that a^b = e^(b*ln(a)):

mc^ml = (e^ln(mc))^ml = e^(ml*ln(mc)) < e^(ml*mc) if ml,mc -> infinity

So, basically, your algorithm complexity upperbound is O(e^(ml*mc)), but we can still shorten it to see, if it's really an exponential complexity. Assume that ml, mc <= N, where N is, let's say, max(ml, mc). So:

e^(ml*mc) <= e^N^2 = e^(e^2*ln(N)) = (e^e)^(2*ln(N)) < (e^e)^(2*N) = [C = e^e] = O(C^N).

So, your algorithm complexity will be O(C^N), where C is a constant, and N is something that growth not faster than linear. So, basically - yes, it is exponetinal complexity.

有更快的方式来实现O(V + E)的答案,但似乎你的问题是关于计算的复杂性,而不是优化算法。

Yes, seems like it's O(mc^ml)
Yes, they bot can be variables in your algorithm complexity

至于你的算法的复杂性:让我们做一些转换,使用的事实,一个B = E(=):

MC ^毫升=(E ^ LN(MC))^毫升= E ^(ML×ln(MC))& lt;E ^(ML MC)如果毫升,MC >;无限

所以,基本上,你的算法复杂度上界为O(E ^(ML MC)),但我们仍然可以把它缩短看,如果真的是一个指数的复杂性。假设毫升,MC和LT;= N,其中n是,让我们说,最大(毫升,MC)。所以:

E(毫升* MC)& LT;= = 2 = 2(e;2 * LN(n))=(e;E);((b));(e;E;);(=。

因此,你的算法复杂度为O(c n n),其中C是常数,n是增长速度不超过线性。所以,基本上是的,这是exponetinal复杂性。

algorithm  time-complexity  complexity-theory