algorithm - 这个递归算法的大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 表示法。我感到困惑的原因是因为用于遍历每个节点的左右子节点的递归。

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

Answer 1

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