优先队列时间复杂度

Question

之前在看堆优先队列对于堆这样的 出队和入队的时间复杂度是 O(logn) 对于 在N个元素中选出前M个元素 是不是时间复杂度应该是Mlogn , logn是选出最小元素的复杂度 要拿出M个元素 所以是不是应该复杂度是MlogN,不知道我这样的说法对不对？

Answer 1

liuyubobobo 2018-07-05 03:20:50

对于我们在这一小节的实现：

我们创建了一个最多包含M个元素的堆。在这个堆上的基本操作是O(logM)的。对于每一个元素，我们都可能要在这个堆上进行一次操作，所以时间复杂度是O(NlogM)的。

如果你一上来对数组中的所有元素组织成一个堆，这个过程是O(N)的，之后在这个巨大的堆中取前M个元素，时间复杂度是O(MlogN)的，综合这个过程，时间复杂度是：O(N + MlogN)的。

后一种方法有一个缺点，或者说是限制，就是需要在算法计算初始，就已知所有的数据。在Leetcode上这个问题中，这个条件可以满足。但是在实际中，数据很有可能是一点一点流进来的，而不是一次性给出的（比如用户的下单数据）；同时，由于N巨大，很有可能维持一个包含N个元素的堆是不现实的，而维持一个包含M个元素的堆，是很简单的。比如要实时统计单笔订单金额最高的前100个订单，前一种方法只需要维护一个包含100个元素的堆，而后一种方法需要维护一个包含订单总量那么多元素的堆，而订单总量可能是一个天文数字：）

• 提问者 xiaocui_0001 #1

  多谢老师。终于明白了。虽然学的比较慢，但是收获很多。

• liuyubobobo 回复 提问者 xiaocui_0001 #2

  继续加油！：）

• 贾斯汀亮 #3

  老师，我没有理解，你的第一段话“我们创建了一个最多包含M个元素的堆。在这个堆上的基本操作是O(logM)的。对于每一个元素，我们都可能要在这个堆上进行一次操作，所以时间复杂度是O(NlogM)的。”
  
  举个例子，1000000个取前100，我用前100个作为堆，循环1000000，即N，也只是吧每个元素跟100个堆中元素求最小，但是100位后面的数据之间，我是指100位后面数据之间没有比较，是不是有问题呢，我还是理解为MlogN，不是Nlog(M)

点开查看后面9条评论