gpt4 book ai didi

python - 为什么尽管 Big-O 相同,但这两个函数的性能却大相径庭?

转载 作者:行者123 更新时间:2023-12-04 02:34:17 25 4
gpt4 key购买 nike

我正在学习大 O 表示法,不是为了上课,只是通过自己阅读来学习。我正在通读 Pythonds 并做了练习,你的任务是编写一个“非最佳”Python 函数来查找列表中的最小数字。该函数应将每个数字与列表中的每个其他数字进行比较:O(n**2)。

这是我想出的:

def myFindmin(alist):
return[x for x in alist if all(x<=y for y in alist)][0]

这是我正在阅读的书给出的内容:

def findmin(alist):
overallmin=alist[0]
for i in alist:
issmallest=True
for j in alist:
if i>j:
issmallest=False
if issmallest:
overallmin=i
return overallmin

显然,书本版本削减了更多变量等,但是根据我的了解,这两个函数的大 O 表示法应该是 O(n**2),不是吗?他们都将每个数字与其他所有数字进行比较,这使得 n**2 成为函数的主要部分,是吗?

但是,当我将 myFindmin() 函数与书中的 findmin() 函数与最佳 min() 函数进行比较时,我得到了三个截然不同的结果:

if __name__=='__main__':
for l in range(1000,10001,1000):
thelist=[randrange(100000)for x in range(l)]
print('size: %d'%l)
for f in[findmin,myFindmin,min]:
start=time()
r=f(thelist)
end=time()
print(' function: %s \ttime: %f'%(f.__name__,end-start))

他们还差得远:

...
size: 8000
function: findmin time: 1.427166
function: myFindmin time: 0.004312
function: min time: 0.000138
size: 9000
function: findmin time: 1.830869
function: myFindmin time: 0.005525
function: min time: 0.000133
size: 10000
function: findmin time: 2.280625
function: myFindmin time: 0.004846
function: min time: 0.000145

如您所见,myFindmin() 不如最优线性 O(n) min() 函数快,但仍然比 O(n**2) findmin() 函数快得多。我认为 myFindmin 应该是 O(n**2) 但它似乎既不是 O(n) 也不是 O(n**2) 那么这里到底发生了什么? myFindmin 的大 O 是什么?

更新

如果我在 all 语句的嵌套循环中添加括号:

def myFindmin(alist):
return[x for x in alist if all([x<=y for y in alist])][0]

这实际上使 myFindmin 始终比 findmin 慢:

size: 8000
function: findmin time: 1.512061
function: myFindmin time: 1.846030
function: min time: 0.000093
size: 9000
function: findmin time: 1.925281
function: myFindmin time: 2.327998
function: min time: 0.000104
size: 10000
function: findmin time: 2.390210
function: myFindmin time: 2.922537
function: min time: 0.000118

所以这里发生的事情是,在 original myFindmin 中,整个列表不是通过列表理解生成的,它实际上是由 all() 本身通过生成器表达式生成的,生成器表达式也执行惰性计算,这意味着一旦发现错误值,它就会停止评估和生成。

如果我添加括号,那么会发生什么情况,列表是通过不执行惰性评估的列表理解生成和评估的。每次将整个列表传递给 all() 进行惰性重新评估之前,都会生成整个列表。

由于原始 myFindmin() 的大 O 为 O(nlogn),新的 myFindmin()(带括号)的大 O 为 O(n^2+nlogn),这反射(reflect)在结果时间中.有关为什么原来的 myFindmin() 是 O(nlogn) 的解释,请参阅我标记为最佳答案的 Amit 的答案。

谢谢大家!

最佳答案

你的代码实际上是O(nlogn) (平均情况)而不是 O(n^2) .

看看all(x<=y for y in alist) ,并回想一下产生 False , 一个元素大于 x 就足够了, no need to go through all valuesalist .

假设您的列表是随机(均匀)打乱的,让我们检查需要遍历多少元素:

x is the highest element: traverse n elements
x is the 2nd highest element: traverse n/2 elements
x is the 3rd highest element: traverse n/3 elements
....
x is the smallest element: traverse 1 element

所以,你的算法的实际复杂度是:

T(n) = n/1 + n/2 + n/3 + ... + n/n =
= n(1 + 1/2 + 1/3 + .... + 1/n)

现在注意 1 + 1/2 + .... + 1/nharmonic series 的总和, 和 it is in O(logn)

这给了你 O(nlogn) 的复杂性而不是 O(n^2)对于平均案例复杂度。

关于python - 为什么尽管 Big-O 相同,但这两个函数的性能却大相径庭?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62581294/

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