使用递归 bsearch 在列表中查找最大值的时间复杂度

Question

抱歉，如果这看起来像一个愚蠢的问题（我是 Big O 的新手），但是 a) 这个函数的时间复杂度基于它的 no 之间有什么区别。比较与 b) 函数整体的时间复杂度？

def bmax(list):
   if len(list) == 1:
       return list[0]
   else:
       middle = len(list)//2
       max1 = bmax(list[0:middle])
       max2 = bmax(list[middle:len(list)])
       if max1 > max2:
          return max1
       else:
          return max2

我推导出它分别是 a) O(n) 和 b) O(logN) 但第二个答案似乎不对，因为根据我的理解，尽管列表在每次递归调用时总是分为 2 个子数组, 比较次数还是n-1?

Answer 1

此函数基于其比较次数的时间复杂度可以通过“计算”在具有 N 个元素的列表上调用该函数时执行了多少次比较来得出。这里有两个直接使用比较的语句：len(list) == 1 和 max1 > max2。显然有 O(N) 次比较。
函数整体的时间复杂度必须考虑到所有的语句。所以它至少会等于之前的复杂度（因此它不可能是 O(logN)）。在这种特定情况下，切片操作确实会花费很多。一般来说，操作 l[i1:i2] 的成本为 O(i2-i1)。有关详细信息，请查看 this 问题。所以我会说在这种情况下总时间复杂度是 O(N^2) 。如果你想提高性能，你可以通过索引而不是使用切片。

def bmax(lst):
    def _bmax(start, end):
        if end - start <= 1:
            return lst[start]
        else:
            middle = start + (end - start) // 2
            max1 = _bmax(start, middle)
            max2 = _bmax(middle, end)
            if max1 > max2:
                return max1
            else:
                return max2
    return _bmax(0, len(lst))

如果您想稍微简化一下代码：

def bmax(lst):
    def _bmax(start, end):
        if end - start <= 1:
            return lst[start]
        middle = start + (end - start) // 2
        return max(_bmax(start, middle), _bmax(middle, end))
    return _bmax(0, len(lst))

Answer 2

正如您正确指出的那样，这里的复杂度仍然是 O(n)，因为您仍然需要进行所有比较。

但是，如果我没记错的话，如果对 bmax 的递归调用是在另一个并行执行的线程中完成的，并且您有无限多个线程，则该函数将在 O(log(n) ) 时间。

使用递归 bsearch 在列表中查找最大值的时间复杂度

Time complexity of finding max value in list using recursive bsearch

python

algorithm

recursion

max

binary-search