2024-05-04 17:16:07 发布
网友
我在看this pycon talk, 34:30,演讲者说获得t元素列表中的n最大元素可以在O(t + n)中完成。
t
n
O(t + n)
怎么可能呢?我的理解是创建堆将是O(n),但是nlargest本身的复杂性是什么,它是O(n + t)还是O(t)(实际的算法是什么)?
O(n)
nlargest
O(n + t)
O(t)
在这种情况下,扬声器是错误的。实际成本是O(n * log(t))。Heapify只在iterable的第一个t元素上调用。这是O(t),但如果t比n小得多,则不重要。然后通过heappushpop将所有剩余的元素添加到这个“小堆”中,一次一个。每次调用O(log(t))都需要heappushpop时间。堆的长度始终保持t。最后,对堆进行排序,这将花费O(t * log(t)),但如果t比n小得多,这也不重要。
O(n * log(t))
heappushpop
O(log(t))
O(t * log(t))
有相当简单的方法可以在预期的O(n)时间内找到第t个最大的元素;例如,see here。在最坏的情况下,要做到这一点有很多困难的方法。然后,在输入的另一个传递过程中,您可以输出t元素>;=第t个最大的元素(在出现重复的情况下会出现冗长的复杂情况)。所以整个工作可以在O(n)时间内完成。
但这些方法也需要O(n)内存。Python不使用它们。实际实现的一个优点是,最坏情况下的“额外”内存负担是O(t),当输入是生成大量值的生成器时,这一点非常重要。
在这种情况下,扬声器是错误的。实际成本是
O(n * log(t))
。Heapify只在iterable的第一个t
元素上调用。这是O(t)
,但如果t
比n
小得多,则不重要。然后通过heappushpop
将所有剩余的元素添加到这个“小堆”中,一次一个。每次调用O(log(t))
都需要heappushpop
时间。堆的长度始终保持t
。最后,对堆进行排序,这将花费O(t * log(t))
,但如果t
比n
小得多,这也不重要。理论的乐趣;-)
有相当简单的方法可以在预期的
O(n)
时间内找到第t个最大的元素;例如,see here。在最坏的情况下,要做到这一点有很多困难的方法。然后,在输入的另一个传递过程中,您可以输出t
元素>;=第t个最大的元素(在出现重复的情况下会出现冗长的复杂情况)。所以整个工作可以在O(n)
时间内完成。但这些方法也需要
O(n)
内存。Python不使用它们。实际实现的一个优点是,最坏情况下的“额外”内存负担是O(t)
,当输入是生成大量值的生成器时,这一点非常重要。相关问题 更多 >
编程相关推荐