时间戳

首页 > 解决方案 > 使用递归 bsearch 在列表中查找最大值的时间复杂度

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

问题描述

抱歉，如果这似乎是一个愚蠢的问题（我是 Big O 的新手），但是 a) 基于其编号的此函数的时间复杂度有什么区别。比较与 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？

标签： pythonalgorithmrecursionmaxbinary-search

解决方案

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

推荐阅读