让我们使用一种算法来查找有向、无环、非加权图中两个节点之间的所有路径，该图中可能在相同的两个顶点之间包含多个边。 (这个 DAG 只是一个例子，请我不是专门讨论这个案例，所以尽管它是正确的，但我认为它是正确的，请忽略它的正确性)。
我们有两个影响因素:
mc :顶点的最大输出边数。 ml :通过边数测量的最大长度路径的长度。 使用迭代方式来解决问题，下面的复杂性代表完成的处理操作的计数。
对于第一次迭代，复杂度 =
mc对于第二次迭代，复杂度 =
mc*mc对于第三次迭代，复杂度 =
mc*mc*mc对于(最大长度路径)第 次迭代，复杂度 =
mc^ml最坏的总复杂度是
(mc + mc*mc + ... + mc^ml) 。1- 我们可以说它是
O(mc^ml) 吗？2- 这是指数复杂度吗？据我所知，在指数复杂度中，变量仅出现在指数处，而不出现在基数处。
3-
mc 和 ml 都是我算法复杂性中的变量吗？ 最佳答案
有一种更快的方法可以在 O(V + E) 中获得答案，但似乎您的问题是关于计算复杂性，而不是关于优化算法。
是的，好像是 O(mc^ml)是的，它们 bot 可以是算法复杂度中的 变量
至于算法的复杂性:让我们使用 a^b = e^(b*ln(a)) 的事实进行一些转换:mc^ml = (e^ln(mc))^ml = e^(ml*ln(mc)) < e^(ml*mc) if ml,mc -> infinity
所以，基本上，你的算法复杂度上限是 O(e^(ml*mc)) ，但我们仍然可以缩短它，看看它是否真的是指数复杂度。假设 ml, mc <= N ，其中 N 是，比方说， max(ml, mc) 。所以: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) 。
因此，您的算法复杂度将是 O(C^N) ，其中 C 是一个常数，而 N 的增长速度不会快于线性。所以，基本上 - 是的，它是指数复杂性。
关于algorithm - 指数复杂度特定情况下的大 O，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30001597/