103.【C语言】数据结构之建堆的时间复杂度分析

1.向下调整的时间复杂度

推导

设树高为h

发现如下规律

按最坏的情况考虑(即调整次数最多)

第1层,有个节点,最多向上调整h-1次

第2层,有个节点,最多向上调整h-2次

第3层,有个节点,最多向上调整h-3次

第4层,有个节点,最多向上调整h-4次

...

第h-1层,有个节点,最多向上调整1次

第h层,有个节点,最多向上调整0次

设T(N)为向下调整的总次数(每层节点数*这一层最坏向下调整多少次)

则有

对于T(N)的求和显然为等差*等比数列的求和,有两种做法:

等差*等比数列的求和

1.错位相减

所以

2.公式法

等差*等比数列的求和公式,计算和的值后再代入中即可求出和

,

因此有

两式子联立可得,的n为h-1

所以

又因为,因此

最终结果

所以

2.向上调整的时间复杂度

推导

设树高为h

发现如下规律

按最坏的情况考虑(即调整次数最多)

第1层,有个节点,最多向上调整1次

第2层,有个节点,最多向上调整2次

第3层,有个节点,最多向上调整3次

第4层,有个节点,最多向上调整4次

...

第h-1层,有个节点,最多向上调整h-1次

第h层,有个节点,最多向上调整h次

设T(N)为向上调整的总次数(每层节点数*这一层最坏向上调整多少次)

则有

计算后有

又因为,因此

最终结果

所以

3.对比

时间复杂度对比

结论:向上调整的时间复杂度为,向下调整的时间复杂度为

对比:向上调整:节点个数多,调整次数多;向上调整:节点个数少,调整次数多;

图像对比

显然随着x越来越大,和的差距会越来越大

4.练习题

题目

求102.【C语言】数据结构之用堆对数组排序文章的HeapSort函数的while循环部分的时间复杂度

分析

错误思路:因为while循环中有AdjustDown,所以为向下调整,时间复杂度为

没有分析代码的执行过程导致出错

看二叉树的最后一层:有个节点,每一个节点调整最多h次,因此属于的求和计算,所以时间复杂度为

5.总结

用堆对数组进行排序,排升序建大堆的时间复杂度总为

对比

void HeapSort(int* arr, int n)
{
    //向上调整建堆时间复杂度为O(N*logN)
	for (int i = 1; i < n; i++)
	{
		AdjustUp(arr, i);
	}

    //排序的时间复杂度为O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[end], &arr[0]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

和

void HeapSort(int* arr, int n)
{
    //向下调整建堆时间复杂度为O(N)
	for (int i = (n-1-1)/2; i >= 0; i--)
	{
		AdjustDown(a,n,i);
	}

    //排序的时间复杂度为O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[end], &arr[0]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

 注意(n-1-1)/2这里把(n-1)视作整体