在最小堆中查找k个最小元素-最坏情况下的复杂性 [英] Finding k smallest elements in a min heap - worst-case complexity
问题描述
我有一个包含 n 个元素的最小堆，并希望从该堆中找到 k 个最小的数字.最坏情况下的复杂度是什么?
I have a minimum heap with n elements and want to find k smallest numbers from this heap. What is the worst-case complexity?
这是我的方法:在堆栈溢出的某个地方，我读到在最小堆中找到第i个最小数字的复杂度是 O(i).因此，如果我们想找到 n-1 个最小的数字(n是无意义的，因为它将是整个堆)，那么总的复杂度应如下所示:
Here is my approach: somewhere on the stackoverflow I read that complexity of finding i-th smallest number in a min heap is O(i). So if we would like to find n-1 smallest numbers (n is pointless, since it would be the entire heap), the total complexity would look something like this:
O(n-1)+ O(n-2)+ O(n-3)+…+ O(2)+ O(1)= O((1 + n-1)*(n/2))= O(n ^ 2)
这正确吗?
推荐答案
不，时间比这要好得多. O(k log(n))非常容易，如果您很聪明，则 O(k).
No, the time is much better than that. O(k log(n)) very easily, and O(k) if you're smart.
从堆中查找和删除最小的元素是 O(log(n)).这很容易导致 O(k log(n))时间.
Finding and removing the smallest element from the heap is O(log(n)). This leads to O(k log(n)) time very easily.
BUT the result that you are thinking about is https://ac.els-cdn.com/S0890540183710308/1-s2.0-S0890540183710308-main.pdf?_tid=382a1cac-e4f7-11e7-8ac9-00000aab0f02&acdnat=1513713791_08f4df78a8821855e8ec788da063ea2f that shows how to find the size of the kth smallest number in time O(k). Now you use the fact that a heap is a binary tree and start from the root and do a recursive search for every number that you find which is smaller than that largest. Then fill out the rest of your list with copies of the k'th smallest number.
在该搜索中，您最终将查找最多不超过该大小的 k-1 ，对于其中一些，您将查找最多2个太大而无法打扰的孩子.最多包含 3k-3 个元素.这使得整个算法为 O(k).
In that search you will wind up looking at up to k-1 that are at most that size, and for some of them you will look at up to 2 children that are too large to bother with, for a maximum of 3k-3 elements. This makes the whole algorithm O(k).
该链接由于bitrot而死亡.希望 https://www.sciencedirect.com/science/article/pii/S0890540183710308持续时间更长.
That link died due to bitrot. Hopefully https://www.sciencedirect.com/science/article/pii/S0890540183710308 lasts longer.
这篇关于在最小堆中查找k个最小元素-最坏情况下的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
