登录
  • #刷题
  • #leetcode

深入探讨下java的PriorityQueue(pq)/TreeMap(tm)/TreeSet(ts)的时间复杂度

mhsasd
1668
5
现在我能确定的是PQ的单次offer/poll都是Log n复杂度; TM,TS的put/get也是Log n的复杂度;给n个元素build一个PQ是O(n)复杂度。一下几个问题是我不太确定的,希望小伙伴们确定下:



  1. build一个pq(从无到有) n次所用时间为O(n),可以不可以说poll一个pq(size为n)一直到空也是O(n)复杂度呢?

  2. 对于TM和TS的一些遍历操作,复杂度又是多少呢?(看有人说是O(n)但是我没有找到确定答案。好像是因为遍历操作的时候并不是对这些数据结构直接操作,而且在一个pre-generated的view上面操作。)



  • for (key : tm.keySet())

  • for (value : tm.values())

  • for (entry : tm.entrySet())



如果有确切的链接解释就更好了。谢谢!
5条回复
热度排序

发表回复