我正在看这个pycon谈话,34:30,发言人说,获取t元素列表中最大的n元素可以完成O(t + n).
怎么可能？我的理解是创建堆将是O(n),但nlargest它本身的复杂性是它O(n + t)还是O(t)(以及实际算法是什么)？
可以说我有一本字典:
{key1:value1........... keyn:valuen}
所以我想说我想写一个函数
def return_top_k(dictionary, k):
return list_of_keys_sorted
获得具有前k个值的键(保持顺序,即最高值键出现在开头......等等),最有效的方法(就大O而言)是多少.