【摘要】
本文从，堆排序的建堆函数与堆调整函数入手，详细解析了堆排序中建堆函数与堆调整函数的时间复杂度，通过剖析源码细节，分别深入了解了函数粗估与精算的时间复杂度。
【正文】
1. 二叉堆实现堆排序源码详见文章：数据结构基础 排序 之 二叉堆实现堆排序
原文链接：
2. 二叉堆建堆代码片
void BuildHeap(int *a,int size) //建立堆 {int i;for(i=size/2;i>=1;i–) //非叶节点最大序号值为size/2{HeapAdjust(a,i,size);}}
3. 二叉堆堆调整代码片
void HeapSort(int *a,int size) //堆排序 {int i;BuildHeap(a,size);for(i=size;i>=1;i–){//cout<<a[1]<<" ";swap(a[1],a[i]);//交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面//BuildHeap(a,i-1);//将余下元素重新建立为大顶堆HeapAdjust(a,1,i-1);//重新调整堆顶节点成为大顶堆} }
4.深入理解堆排序时间复杂度
因此。复杂度的上界很好理解，为(N/2)*LgN，即O(NLgN)。但是这并不是一个紧绷的复杂度，仔细想想也知道根本没进行(N/2)*LgN那么多次。
4.3 深入理解算法步骤
4.3.1 所有的叶节点都不进行堆调整；
4.3.2 堆调整函数是从高度为1的节点开始进行直到根为止。所以，这时候我们需要理解调整函数的执行过程，不能单纯的理解为LgN。而且，对于高度为1的节点，至多替换发生1次；对于高度为2的节点，至多替换发生2次，，以此类推，对于高度为h的节点，至多发生替换h次。我们知道，堆是满树，叶节点共有N/2个，它们的高度是0 。高度为1的节点正是他们的父节点，共有(N/2)/2个。高度为2的，类推有((N/2)/2)/2个。因此高度为h的共有N/（2的（h+1）次方）个。
4.4 计算算法复杂度
堆的高度总共只有0到LgN，现在每个高度的节点个数清楚，每个高度的每个节点至多发生的替换次数也清楚，则总共发生的替换数也就清楚了：
4.4.1 (N/(2的(h+1)次方)) * h 的求和 。
(h取值0~LgN)N是常数，简化一下变成(N/2) * ( h / (2的h次方) ) (h取值0~LgN)；
4.4.2 接下来就是一个级数求和问题了。求 ( h / (2的h次方) ) (h取值0~LgN)。
设结果为S
有，S = 1/2 + 2/(2的2次方) + 3/(2的3次方) … + LgN/ (2的LgN次方)。
有，S*(1/2) = 1/(2的2次方) + 2/(2的3次方) + 3/(2的4次方)…+LgN/(2的(LgN+1)次方)。
两式错位相减
有，S*(1/2) = 1/2 + 1/(2的2次方) + 1/(2的3次方) … + 1/ (2的LgN次方) – LgN/(2的(LgN+1)次方)。
右式前边几项为等比数列，最终化简结果为
S = 2 – (1/2)的(LgN-1)次方-LgN / ( 2的LgN次方)。
当N趋向于无穷大时，右式的二，三两项都趋近于0，于是limS = 2。
所以，我们要求的建堆复杂度为O( (N/2) * S ) = O(N)。
5.算法小结
从上述推导过程可以看出，重点在于根据建堆函数找出计算复杂度的算式，然后利用求级数，求极限的方法解出结果。其实最终还是回归了理解算法和合理利用数学工具上。
但是这并不是一个紧绷的复杂度，仔细想想也知道根本没进行(N/2)*LgN那么多次。
版权声明：本文为博主原创文章，未经博主允许不得转载。
我们一直在旅行，一直在等待某个人可以成为我们旅途的伴侣，
