find a peak算法的增长阶是多少？该递归代码复杂度为O(logn)吗？

首先给出明确结论：这段代码的实际时间增长阶为O(logn)，你之前的认知存在偏差——并非所有递归实现的算法增长阶都是O(n)，递归算法的复杂度需要结合单次递归操作耗时、每次递归缩小的问题规模共同判断。

复杂度推导过程 #

• 单次递归操作耗时：每次调用函数仅做了中间索引计算、相邻元素比较共3次以内的常数操作，无遍历类线性操作，单次耗时为O(1)。
• 问题规模变化：每次递归只会选择左半区间或者右半区间继续搜索，每次递归后待搜索的区间长度直接缩小为原来的1/2，和二分查找的规模收缩逻辑完全一致。
• 总递归次数：对于长度为n的数组，最多需要log₂n次递归就会触发终止条件返回结果。

总时间复杂度 = 单次递归耗时 * 总递归次数 = O(1) * O(logn) = O(logn)，完全符合你的算法复杂度要求。

认知误区澄清 #

你会觉得递归方法增长阶为O(n)，大概率是和「每次递归仅将问题规模缩小1」的递归逻辑混淆了，比如递归实现阶乘计算、递归遍历数组这类场景，总递归次数为n次，对应复杂度才是O(n)，和当前这段二分类递归的逻辑有本质区别。

内容的提问来源于stack exchange，提问作者sith69