gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:19:02 24 4
gpt4 key购买 nike

我需要展示迭代和递归二进制搜索算法“渐近运行时分析”之间的差异。据我所知,它们具有相同的最坏情况复杂度(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)

最佳答案

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

它们在空间使用方面有所不同——递归二进制搜索将使用 log(n) 空间(因为堆栈),除非尾调用被编译器删除并变成非递归定义。

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

关于python - 在渐近分析的情况下,迭代和递归二进制搜索算法有什么区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7780206/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com