迭代与递归二分查找算法在渐近分析中的区别是什么

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)）。