algorithm - 计算递归函数的大O

Question

我有一个检查数组是否为堆的方法。在每次递归调用时，我在左子树和右子树上创建 2 个新的递归调用来遍历节点并检查它们的值是否正确。

我想计算这个的 BigO。我认为在最坏的情况下它是 O(n) 因为如果它是一个堆，那么它永远不会提前停止并且需要访问每个节点。我认为最好的情况是 O(3)，当它检查第一个左子树和右子树并且都返回 false(不是堆)时会发生这种情况。

我的问题是:这个逻辑有意义吗？我认为确实如此，但每当我看到递归函数的时间复杂度时，它们似乎总是处于某种对数时间形式。几乎没有人明确说明递归函数具有某种神秘的性质。为什么递归函数经常以对数时间处理事物？我的上述逻辑是否有效？

Answer 1

是的，这是有道理的。您看到大多数算法采用对数时间的原因是因为它重复某些内容并不断将范围除以某个因素。