为什么heappop时间复杂度在python中是O(logn)(不是O(n))？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了为什么heappop时间复杂度在python中是O(logn)(不是O(n))？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含652字，纯文字阅读大概需要1分钟。

内容图文

对于列表,heappop将弹出前面的元素.从列表前面删除元素的时间复杂度为O(n).
我想念什么吗？

解决方法:

一个heappop()重新排列列表中的log(n)元素,这样它就不必移动每个元素.

这很容易看出：

>>> from random import randrange
>>> from heapq import heapify, heappop
>>> h = [randrange(1000) for i in range(15)]
>>> heapify(h)
>>> h
[80, 126, 248, 336, 335, 413, 595, 405, 470, 592, 540, 566, 484, 970, 963]
>>> heappop(h)
80
>>> h
[126, 335, 248, 336, 540, 413, 595, 405, 470, 592, 963, 566, 484, 970]
>>> #       ^----^---------^----^----^----^----^---------^----^----^--- elements that didn't move

请注意,弹出操作没有移动大多数元素(例如248在heappop之前和之后处于相同位置).

内容总结

以上是互联网集市为您收集整理的为什么heappop时间复杂度在python中是O(logn)(不是O(n))？全部内容，希望文章能够帮你解决为什么heappop时间复杂度在python中是O(logn)(不是O(n))？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端