algorithm - 两个嵌套循环的简单算法复杂度

Question

我想这很简单，但似乎我在麻烦自己..

下面的复杂度是多少？

// let's say that Q has M initial items
while Q not empty
  v <- Q.getFirst

  for each z in v // here, every v cannot have more than 3 z's
    ...
    O(1) operations here
    ...
    Q.insert(z)
  end
end

这种情况发生的次数，取决于在某个时候 v 是否没有更多的 z(我们称这个数字为 N)

复杂度是 O(MxN^2) 还是我错了？这就像有一棵树有 M 个父节点，每个节点最多可以有三个 child 。 N为节点总数。

Answer 1

你的算法复杂度应该有一个上限 O( (M * v) - 父节点是子节点 ) 最好表述为 O(n) 其中 n 是树中的节点数，因为你只迭代树一次。

根据您的操作，您需要考虑 Q.insert(z) 和 Q.getFirst() 操作的运行时间，因为这取决于您的数据可能值得考虑的结构。

假设 Q.insert() 和 Q.getFirst() 运行时间是 O(1)，你可以说 O(M * v) 是一个近似边界，但是由于 v 元素可以重复，所以最好声明运行时只是 O(n)，因为 O(m*v) 实际上在所有情况下都高估了上限。 O(n) 对于树的每个实例都是精确的(n 是节点数)。

我会说将它称为 O(n) 更安全，因为我不知道您的插入的确切实现 - 尽管对于链接列表，插入和首先获取都可以是 O(1) 操作。 (如果正确实现，大多数二叉树插入将是 O(log n) - 没有提供足够的信息)

谨慎行事并考虑您的运行时分析 O(n) 应该不会对您造成伤害，但根据您向谁推销它，这个额外的变量似乎是不必要的。

HTH

已编辑:评论中问题的清晰度帮助我更好地理解了问题，修正了废话