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

Question

我正在学习 Big-O 表示法，不是为了 class，只是通过自己阅读来学习。我正在通读 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

显然，书本版本削减了更多的变量等等，但是，根据我的了解，这两个函数的 Big-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)，这反映在结果倍。有关为什么原来的 myFindmin() 是 O(nlogn) 的解释，请参阅我标记为最佳答案的 Amit 的答案。

谢谢大家！

Answer 1

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

看看all(x<=y for y in alist)，回想一下要得到False，一个元素大于x、no need to go through all values of [=17]就足够了=].

假设您的列表是随机（均匀）打乱的，让我们检查需要遍历多少元素：

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 是 harmonic series, and it is in O(logn)

的总和

这为您提供了 O(nlogn) 的复杂度，而不是 O(n^2) 的平均情况复杂度。

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

Why is the performance of these two functions so drastically different despite the same Big-O?

python

algorithm

big-o

time-complexity