作业帮 > 数学 > 作业

数据结构:关于堆排序的时间复杂度分析,这段该如何分析呢?

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/17 11:07:06
数据结构:关于堆排序的时间复杂度分析,这段该如何分析呢?
在正式排序时,第i次取堆顶记录重建堆需要用O(logi)的时间(完全二叉树的某个结点到根结点的距离为log2i+1),并且需要取n-1次堆顶记录,因此,重建堆的时间复杂度为O(nlogn).
这里的log2i+1是怎么算出来的呢?
数据结构:关于堆排序的时间复杂度分析,这段该如何分析呢?
这就是完全二叉树的性质啊,n个结点的完全二叉树的高度