本文主要是介绍关于堆排序建堆时间复杂度的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
建堆的过程，看起来外面一层循环O(n)，里面是个logn的调整函数，时间复杂度貌似是nlogn的，但是仔细分析，其实质是O(n)的。
证明如下：
首先，对于高度为h的完全二叉树，其第i层的元素个数为2^(i-1)，对于堆的每一层，调整的深度都不一样，每层的元素的调整深度小于等于h-i，假设每层调整的深度是h-i，欲构建的堆是个完全二叉树，那么对于每层来说：
最后一层不用调整；
倒数第二层的消耗是：2^(h-1)*1；
倒数第三层的消耗是：2^(h-2)*2；
。。。。。。
第一层的消耗是：2^(h-h)*(h-1)；
加起来总消耗是：S=2^(h-1)*1+2^(h-2)*2+。。。+h；
2S=2^h*1+2^(h-1)*2+。。。+2*h；
S=2^h+2^(h-1)+2^(h-2)+。。。+2^1-h；
S=2^h+2^(h-1)+2^(h-2)+。。。+2^1+2^0-h-1；
S=2^(h+1)-2-h；
h=logn；
代入得：S=2*n-2-logn；
故堆排序的建堆过程是O(n)的。
这篇关于关于堆排序建堆时间复杂度的证明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
