为什么这两个函数的表现如此不同，尽管它们具有相同的大 O 复杂度？

Question

为什么这两个函数的表现如此不同，尽管它们具有相同的大 O 复杂度？

3

我正在学习大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]

这实际上使得我的findmin函数比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

所发生的情况是，在原始的myFindmin中，整个列表不是通过列表推导式生成的，而是通过all()本身生成的生成器表达式生成的，这也执行了惰性评估，这意味着它在找到假值时停止评估和生成。

如果我添加括号，那么列表会通过列表推导式生成和评估，在传递给all()进行惰性重新评估之前，每次都会生成整个列表。

由于原始的myFindmin()具有O(nlogn)的时间复杂度，新的myFindmin()（带有括号）将具有O(n^2 + nlogn)的时间复杂度，这反映在结果时间中。关于为什么原始的myFindmin()是O(nlogn)，请参见我标记为最佳答案的Amit的回答。

谢谢大家！

- Jon Red

2

从书中的版本来看，“a”是什么？ - Barmar

列表推导式的实现与for循环的实现在底层上是不同的。在某些情况下，列表推导式比for循环更快。https://medium.com/quick-code/python-one-liner-list-comprehension-24e35a20bd1d - IjonTichy

1

all()在最坏情况下仅为O(n)。如果它找到一个falsy值，它会提前退出。 - jasonharper

@IjonTichy 这并不能解释这种差异的程度。而列表推导式本质上是在幕后使用for循环完成的，只是进行了一些轻微的优化。这些差异是微不足道的，而不是数量级上的。 - juanpa.arrivillaga

@JonRed all 不行，列表推导式可以。 - juanpa.arrivillaga

显示剩余6条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

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

看一下 all(x<=y for y in alist)，回想一下为了得到 False，只需要有一个元素比 x 大即可，无需遍历所有值。

假设你的列表是随机洗牌的（且均匀分布），让我们来看看需要遍历多少元素：

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/n 是调和级数的总和，并且O(logn)算法可以计算它。

这使得平均情况下的复杂度为O(nlogn)而不是O(n^2)。