这个递归算法的大O

Question

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

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 除外）。但是我到底该如何计算这种递归解决方案的运行时间呢？

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

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

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

Answer 4

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

如果父节点（节点）== NULL

，但必须添加 node != 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 是堆中最小值的数量。

享受。