Python HeapSort时间复杂度
Python HeapSort时间复杂度
提问于 2017-03-27 03:10:25
我为HeapSort编写了以下代码，它运行良好：
class Heap(object):
def __init__(self, a):
self.a = a
def heapify(self, pos):
left = 2*pos + 1
right = 2*pos + 2
maximum = pos
if left < len(self.a) and self.a[left] > self.a[maximum]:
maximum = left
if right < len(self.a) and self.a[right] > self.a[maximum]:
maximum = right
if maximum != pos:
self.a[pos], self.a[maximum] = self.a[maximum], self.a[pos]
self.heapify(maximum)
def buildHeap(self):
for i in range(len(self.a)/2, -1, -1):
self.heapify(i)
def heapSort(self):
elements = len(self.a)
for i in range(elements):
print self.a[0]
self.a[0] = self.a[-1]
self.a = self.a[:-1]
self.heapify(0)
def printHeap(self):
print self.a
if __name__ == '__main__':
h = Heap(range(10))
h.buildHeap()
h.printHeap()
h.heapSort()但是，由于列表切片，这里的函数heapSort似乎需要时间O(n^2)。(对于大小为“n”的列表，将其切片为“n-1”将花费O(n-1)时间)。有人能确认一下我的想法是否正确吗？如果是，heapSort函数中的最小变化应该是什么，才能使它在O(nlogn)中运行？
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-03-27 03:26:12
是的，我相信你是对的。为了使它更快，替换如下的东西：
self.a = self.a[:-1]通过以下方式：
self.a.pop()列表的pop()成员函数删除并返回列表中的最后一个元素，具有恒定的时间复杂度。
lists作为连续内存存储，这意味着list的所有元素都是一个接一个地存储的。这就是为什么在list的中间插入一个元素是如此昂贵的原因: Python必须在插入的位置之后移动所有的元素，这样才能为新元素腾出空间。但是，简单地删除list末尾的元素所需的时间可以忽略不计，因为Python只需要删除该元素。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43037352
复制相关文章
相似问题
腾讯云开发者
