0

我有一个算法，它采用一个有n节点的 DAG 图，对于每个节点，它在其邻接节点上进行二进制搜索。据我所知，这将是一种O(n log n)算法，但是由于n日志内部仅对应于节点的邻接关系，因此我想知道这是否会变得相当O(n log m)。m我的意思是m与每个节点相邻的节点（直观且通常远小于n）。

为什么不O(n log m)呢？我会说O(n log m)没有意义，因为m在技术上不是输入的大小，n是。此外，最坏的情况m可能是n因为一个节点可以很容易地连接到所有其他节点。正确的？

4

4 回答 4

3

这里有两种情况：

  1. m，相邻节点的数量由一个常数限制C，并且
  2. m, 相邻节点的数量仅受n, 节点数量的限制

在第一种情况下，复杂度是O(n)，因为Log(C)是一个常数。在第二种情况下，这是O(n*log(n))因为您在问题中解释的原因（即“m可以是” n）。

于 2012-09-16T12:30:27.833 回答
0

大 O 表示法提供了算法复杂度的上限，因此由于 m 在最坏的情况下等于 n（准确地说是 n - 1），因此正确的复杂度将是O(n log n)。

于 2012-09-16T12:29:50.400 回答
0

肯定有一个节点连接到每个其他节点的 DAG。另一个示例是节点编号为 0,1,2...n 的 DAG，其中每个节点都有一条通往所有更高编号节点的边。

给出取决于多个参数的复杂性估计是有先例的 - http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm引用了 O(|E| + |V| log(|V|) 的成本. 在某些情况下，这可能是有用的信息。

于 2012-09-16T12:31:08.683 回答
0

正确的是，在图的最坏情况下，每个节点都有 n-1 个邻居，这意味着它连接到其他所有人，但如果每个节点都是这样，那么它就不是无环图。因此每个节点的平均邻居小于n。

DAG 中的最大边数为：(n-1)n/2

如果我们查看每个节点，它将具有 (n-1)/2 个邻居的平均值。因此，在最坏的情况下，您的复杂性仍将保持O(n log n) 。

于 2012-09-16T12:43:15.373 回答