英文:
Why is the time complexity of heapq.merge higher than that of heapq.heapify?
问题
使用heapq.merge合并包含总共n个元素的k个排序列表应该具有O(n * logk)的复杂度。虽然这并没有直接列在文档中，但可以从维基百科文章中提到的直接k路合并中推断出来。这也似乎相当直观 - 你创建一个包含k个顶部元素的堆，然后弹出堆的根元素并将下一个元素从相同列表推入堆中 - 重复此操作直到堆（和供给它的列表）为空。
让我感到困惑的是，如果将heapq.heapify应用于以单个未排序列表提供的相同数量的元素n，那么该算法的复杂性高于后者。后者的复杂性已知为O(n)
这是没有道理的 - 应该是相反的。堆化n个无序元素应该比堆化相同的元素作为k个列表中的排序元素更困难。
我在这里漏掉了什么？
英文:
Merging k sorted lists containing a total of n elements using heapq.merge is supposed to have a complexity of O(n * logk). This is not directly listed in the documentation but can be inferred from the Wikipedia article mentioning the direct k-way merge. It also seems fairly intuitive - you create a heap of the k top elements and then pop the root of that heap and push onto the heap the next element from the same list - and repeat this till you get the heap (and the lists feeding to it) empty.
What bugs me is that the complexity of this algorithm is higher than that of heapq.heapify if the latter is applied on the same number of elements n supplied in a single unsorted list. The latter complexity is known to be O(n)
This does not make sense - it should be the other way round. It should be more difficult to heapify n unordered elements than to heapify the same elements as sorted in k lists.
What am I missing here?
答案1
得分: 2
直接的k路合并从已排序数组的输入中产生一个排序数组。
从所有未排序的n元素创建一个堆会产生一个堆。
堆不是一个排序列表；事实上，你需要做大量的工作才能从堆中产生一个排序列表，如有关堆排序的文章所讨论，它是一个O(n log n)的排序算法。因此，创建堆可能是O(n)，但输出与k路合并的输出不同。在这个上下文中，您可以将它视为比已排序数组弱。因此，这个时间复杂度比k路合并的时间复杂度小是有道理的。
英文:
Direct k-way merge produces a sorted array from your input of sorted arrays.
Creating a heap from all your n elements in unsorted order produces, well, a heap.
A heap is not a sorted list; in fact you need to do a lot of work to produce a sorted list from a heap, as discussed in articles about heapsort, which is an O(n log n) sorting algorithm. So creating the heap may be O(n), but the output is different to that of k-way merge. In this context, you may view it as weaker than the already sorted array. Thus, it makes sense that this time complexity is smaller than that of k-way merge.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论