0

我做了以下涉及二进制堆结构的算法：

Algorithm: heapMinimum(node)
Input    : Position n
Output   : Sequence minList; containing the postions that hold the minimum value

1. minList <-- sequence
2. if parent(node) == NULL // current node is the root of the tree
3.   minList.insertLast(node)
4. if (leftchild(node).element() == node.element())
5.   concat(heapMinimum(leftchild(node), minList))
6. if(right(node).element() == node.element())
7.   concat(heapMinimum(rightChild(node), minList))
8. return minList

该算法所做的基本上是遍历给定其根的二叉堆，以查找并存储保存最小值（即与根的值匹配的值）的节点。

现在，我无法以大 O 表示法计算算法的运行时间。我感到困惑的原因是因为用于遍历每个节点的左右子节点的递归。

所有操作都在恒定时间内运行O(1)，除了concat。但是我该如何计算这种递归解决方案的运行时间呢？

4

4 回答 4

4

对我来说看起来像 O(N)，其中 N 是元素的数量。如果您的堆只包含相等的元素，则将遍历所有元素。另外，为什么不是 concat O(1)？只要您“连接”数字，它也应该是 O(1)。但是，如果 concat 以某种方式是 O(N) （从您的伪代码看起来是这样 - 但是您应该重新考虑是否真的需要连接两个返回的列表），那么总时间将是 O(N 2 ) 最坏的情况。

于 2010-02-20T15:22:24.173 回答
1

我假设您在谈论二进制堆？

根据堆属性的定义，您应该只递归直到找到一个大于根的元素。但是，您还必须确定树的当前级别上的其他元素都不与根的大小相同。本质上，这会产生这样的规则：一旦遇到大于根的堆元素，就不需要递归到元素的子元素。

然而，在最坏的情况下，每个元素都可能等于根。在这种情况下，您必须检查整个堆，这会产生 O(n) 时间，其中 n 是堆中的元素数。

所以要回答你的问题，它是 O(n)

于 2010-02-20T15:22:32.563 回答
0

正如其他人所提到的，如果你的 concat() 是 O(1) [如果不是，你可以这样做] 那么你的算法在输出大小上是 O(N)。

但是，如果您使用复制列表的 concat() （取决于系统，这很容易意外做到），那么最坏的情况是输出大小为 O(N^2)。导致此行为的一种情况是，当您的最小节点深入到树中时，您的 concat() 会不断复制每个级别的列表。

请注意，此深度受堆深度的限制，因此如果您的树是平衡的，那么最坏的情况也是数据结构大小的 O(M log M)。您可以看到这一点，因为最大副本数是树的深度。

于 2010-02-20T18:42:16.583 回答
0

我想您的解决方案中有错误。第一次检查：

如果父（节点）== NULL

必须删除，但必须添加节点 != NULL的检查。

此外，我建议使用 list 作为附加参数，您将在其中放置答案。所以，这是我的实现：

Algorithm: heapMinimum(node, minList)
if (node != NULL)
{
   if (minList.empty() || minList.getFirst().element() == node.element())
   {
      minList.insertLast(node)

      heapMinimum(left(node),  minList)
      heapMinimum(right(node), minList)
   }
}

假设向列表中添加一个元素需要 O(1)，我们得到该函数需要 O(k)，其中 k 是堆中最小值的数量。

享受。

于 2010-02-23T15:13:16.077 回答