询问mystery递归算法的时间复杂度是否为O(logN)（基于元素数N）

先看给定的递归函数代码：

def mystery(mylist, first, last):
     if (first == last):
        return mylist[first]
     mid = (first + last) // 2
     return min(mystery(mylist, first, mid), mystery(mylist, mid+1, last))

这个函数的功能是通过分治法找出数组区间[first, last]内的最小值。

时间复杂度结论 #

该算法的时间复杂度是O(N)，并非你猜测的O(logN)。

原因分析 #

你提到的“每次调用将数组规模减半”没错，但关键区别在于：

• 二分查找这类O(logN)的算法，每次递归只会选择处理其中一半子数组；
• 而这个函数必须递归处理左右两个子数组，每个元素都会在递归的最底层（first == last的情况）被访问一次，总共有N次基础操作。

用递推公式验证：
设T(N)为处理N个元素的时间开销：

1. 递归基：当N=1时，T(1) = O(1)（直接返回元素）；
2. 递归步骤：T(N) = 2*T(N/2) + O(1)（拆分两个N/2的子问题，加一次min比较操作）。

根据主定理计算，a=2，b=2，f(N)=O(1)，满足主定理第一种情况，最终T(N)=O(N)。

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