0

我有一种算法可以在无向图中找到一组边不相交的路径。

  1. 从图中所有边的列表开始

  2. 当列表中仍有可用边时，执行深度/广度优先搜索以找到路径。如果找到路径，保存它，从列表和图形中删除边并增加路径计数器

  3. 从列表中删除第一个可用边并将其指定为当前路径

  4. 尝试将当前路径与已保存边缘列表匹配

  5. 如果没有可用的边缘匹配，则路径完成

  6. 如果可用边可以扩展当前路径，则将其添加到当前路径并从边列表中删除，然后继续尝试扩展当前路径。

我相信 2 和 3 在 O(E(V+E) + E) 时间内执行，因为

  • 广度/深度优先搜索在 O(V+E) 时间内执行
  • 搜索在列表中的 E 条边上执行
  • 从列表和图形中删除 E 边

由于迭代边缘列表需要两个循环，算法的后半部分在 O(E^2) 时间内执行。

因此，我有一个最后的最坏情况 O(E(V+E)+ E^2+E)=O(EV+2E^2+E)

我对吗？

4

1 回答 1

1

不，这是不对的。据我了解您的问题 O(E(V+E)+ E^2+E) 是正确的。但在大 O 表示法中，人们会因为复杂性而选择“最大”事件。您在其中具有三个复杂性类：

  1. E(V+E)
  2. E^2
  3. 乙

第 3 点被第 2 点消除了，因为在任何情况下 2 都更大。在“最坏情况”中，E 是 V^2。知道了这一点，您可以确定第 1 点是最大复杂性部分（V^3+V^4 > V^4）。你的算法是正确的，你对零件的假设也是正确的，所以这个问题的算法复杂度是：O(E(V+E))

你可以看看这些幻灯片。在幻灯片 23 中记录了复杂性并适合您的计算；）

于 2013-04-21T11:40:22.220 回答