a**q
发帖数: 3 | 1 假设一共有n个节点。我说复杂度是nlogk，但是面试官说复杂度就是n。我问他为什么
，他说因为是建堆，堆不是完全排好序的，所以不用logk用1就可以了。我当时比划了
两下还是觉得应该是logk，但是因为面试时间有限就没有当场深究。现在又想了一下，
确实应该是nlogk而不是n，一个特例是假设k=n，那么就相当于排序，复杂度nlogn。我
该怎么办呢？是发邮件告诉面试官应该是nlogk还是坐以待毙？ |
l*********8
发帖数: 4642 | 2 的确是nlogk
【在 a**q 的大作中提到】
: 假设一共有n个节点。我说复杂度是nlogk，但是面试官说复杂度就是n。我问他为什么
: ，他说因为是建堆，堆不是完全排好序的，所以不用logk用1就可以了。我当时比划了
: 两下还是觉得应该是logk，但是因为面试时间有限就没有当场深究。现在又想了一下，
: 确实应该是nlogk而不是n，一个特例是假设k=n，那么就相当于排序，复杂度nlogn。我
: 该怎么办呢？是发邮件告诉面试官应该是nlogk还是坐以待毙？
|
f*******n
发帖数: 12623 | 3 的确是nlogk。O(1)可以拿到top element，但是要remove它，还是要O(log k)。
假如k=n，那按照他说的就可以用这个方法O(n)去sort一个unsorted的array了。 |
s******n
发帖数: 3946 | |
w****x
发帖数: 2483 | 5 nlogk, 怎么会是O(n),
不过现实当中我觉得merge k array用堆不一定比不用直接比较的O(n*k)快, 甚至更慢 |
l*********8
发帖数: 4642 | 6 it depends on how large k is.
【在 w****x 的大作中提到】
: nlogk, 怎么会是O(n),
: 不过现实当中我觉得merge k array用堆不一定比不用直接比较的O(n*k)快, 甚至更慢
|
