我有一个检查数组是否是堆的方法。在每次递归调用时，我在左侧子树和右侧子树上创建 2 个新的递归调用来遍历节点并检查其值是否正确。
我想计算这个的 BigO。我认为在最坏的情况下它是 O（n），因为如果它是一个堆，那么它永远不会提前停止并且需要访问每个节点。我认为最好的情况是 O（3），当它检查第一个左子树和右子树并且都返回 false（不是堆）时，就会发生这种情况。
我的问题是：这个逻辑有意义吗？我认为确实如此，但是每当我看到递归函数的时间复杂度时，它们似乎总是处于某种形式的对数时间。这几乎就像递归函数具有某种神秘的品质，没有人明确指出。为什么递归函数经常在对数时间内处理事物？我的上述逻辑有效吗？
是的，这是有道理的。你看到大多数算法需要对数时间的原因是因为它重复某些东西，并不断将范围除以某个因素。
是的，这是有道理的。主定理的三种情况中只有一种（尽管可以说是最有趣的）具有对数。