algorithm - 大 O 复杂度 O(n log n) vs O(n log m)

Question

我有一个算法，该算法采用具有 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，因为一个节点可以很容易地连接到所有其他节点。正确的？

Answer 1

这里有两种情况:

1. m，相邻节点的个数以常数C为界，而
2. m，相邻节点数仅受n，节点数
限制

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