指数级复杂度的特定情况下的大O表示法

Question

让我们设计一个算法来查找有向无环非加权图中两个节点之间的所有路径，这些路径可能包含同一两个顶点之间的多条边。（此DAG仅为示例，请不要特别讨论此情况，尽管它是正确的，但请忽略它的正确性。）

我们有两个影响因素：

1. `mc`：每个顶点的最大出边数。 2. `ml`：以边数为度量单位的最长路径长度。

使用迭代方法解决问题，其中复杂性表示已完成的处理操作数。

第一次迭代的复杂度为 `mc`。

第二次迭代的复杂度为 `mc*mc`。

第三次迭代的复杂度为 `mc*mc*mc`。

第 `(max length path)` 次迭代的复杂度为 `mc^ml`。

总最坏复杂度为 `(mc + mc*mc + ... + mc^ml)`。

1. 我们可以说它是 `O(mc^ml)` 吗？ 2. 这是指数复杂度吗？据我所知，在指数复杂度中，变量只出现在指数中，而不是在底数中。 3. 在我的算法复杂度中，`mc` 和 `ml` 都是变量吗？

- Median Hilal

---

如果你的图是无环图，则两个节点之间仅存在 0 或 1 条路径。 - Chan Kha Vu

@FalconUA - 这并不适用于有向无环图。 - libik

哦，抱歉，没有仔细阅读问题。 - Chan Kha Vu

可能是重复的问题：如何在DAG中找到给定节点集合的所有路径？ - Benjamin Gruenbaum

我编辑了问题以更清楚地阐述，“可能包含同一两个顶点之间的多条边”，澄清：考虑一个简单（甚至极端）的三个顶点v1、v2、v3和六条边e1、...、e6的情况，其中前三条边连接v1和v2，后三条边连接v2和v3。因此，我们有3*3=9条路径，e1e4、e1e5、e1e6、e2e4、...、e3e6。嗯，这具有指数增长，不能与我们的具有3个顶点和6条边的图形大小线性增长。然而，请专注于复杂度，不要离开我的DAG。 - Median Hilal

Answer 1

有一种更快的方法可以在 O(V + E) 的时间内得出答案，但似乎您的问题是关于计算复杂度，而不是优化算法。

是的，看起来它是 O(mc^ml)
是的，它们都可以成为您算法复杂度中的变量

至于您的算法复杂度：让我们进行一些转换，利用 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 是不以更快的速度增长的东西。所以，基本上 - 是的，它是指数复杂度。

- Chan Kha Vu

---

谢谢。然而，我不明白为什么要寻找复杂度上界为O(e^(ml x mc))的结果，如果它本来就是O(mc^ml)的上界，而且O(mc^ml) < O(e^(ml x mc))！即使你的结论是正确的，我也无法理解你的观点。考虑到其中一个变量是常数，这样公平吗？如果两个变量都趋近于无穷大会怎样？至于您提出的更快的O(mc + ml)方法，请查看我在此问题上的提问：http://stackoverflow.com/questions/29995965/finding-all-paths-between-a-set-of-vertices-in-a-dag - Median Hilal

请注意，我的DAG可能包含同一两个顶点之间的多条边。举个简单（甚至极端）的例子，有三个顶点v1、v2、v3和六条边e1、...、e6，其中前三条边连接v1和v2，后三条边连接v2和v3。因此，我们有3*3=9条路径，即e1e4、e1e5、e1e6、e2e4、...、e3e6。这具有指数增长，无法与我们的具有3个顶点和六条边的图形大小线性增长。 - Median Hilal