在渐近分析的情况下，迭代和递归二分搜索算法有什么区别

Question

我需要展示迭代和递归二分搜索算法的“渐近运行时分析”之间的差异。据我所知，它们具有相同的最坏情况复杂度（O（log（n）），但在某些资源中它说递归具有O（log（n）+1）。我有点困惑，有人可以帮助我关于这种情况？

使其运行时间与下面编写的代码相同。

我还需要改进 python 递归二分搜索算法，

def binarySearch(alist,item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)/2
        if alist[midpoint] == item:
            return True
        else:
            if item<alist[midpoint]:
                return binarySearch(alist[:midpoint],item)
            else:
                return binarySearch(alist[midpoint+1:],item)

Answer 1

O(log(n) + 1) 与 O(log(n)) 相同——渐近地，它们产生相同的函数集。常数加法被忽略，就像常数倍数一样。

它们在空间使用方面有所不同——递归二分搜索将使用 log(n) 空间（因为堆栈），除非尾部调用被编译器删除并转换为非递归定义。

无论如何，您的算法在性能上会显着下降，因为切片非常昂贵（O(n)）。