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

发布于:2024-11-29 ⋅ 阅读:(30) ⋅ 点赞:(0)

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

推导

设树高为h

39e01bdbb5cc491caf615aa7cf366d3d.png

发现如下规律

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

第1层,有eq?2%5E0个节点,最多向上调整h-1次

第2层,有eq?2%5E1个节点,最多向上调整h-2次

第3层,有eq?2%5E2个节点,最多向上调整h-3次

第4层,有eq?2%5E3个节点,最多向上调整h-4次

...

第h-1层,有eq?2%5E%7Bh-2%7D个节点,最多向上调整1次

第h层,有eq?2%5E%7Bh-1%7D个节点,最多向上调整0次

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

则有eq?T%28N%29%3D2%5E0*%28h-1%29+2%5E1*%28h-2%29+2%5E2*%28h-3%29+...+2%5E%7Bh-2%7D*1

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

等差*等比数列的求和

1.错位相减

eq?T%28N%29%3D2%5E0*%28h-1%29+2%5E1*%28h-2%29+2%5E2*%28h-3%29+...+2%5E%7Bh-2%7D*1

eq?2*T%28N%29%3D0+2%5E1*%28h-1%29+2%5E2*%28h-2%29+2%5E3*%28h-3%29+...+2%5E%7Bh-1%7D*1+0

所以eq?T%28N%29%3D2%5Eh-h-1

2.公式法

等差*等比数列的求和公式eq?S_n%3D%28An+B%29*q%5En-B,计算eq?S_1eq?S_2的值后再代入eq?S_n中即可求出eq?Aeq?B

eq?S_1%3D2%5E0*%28h-1%29,eq?S_2%3D2%5E0%28h-1%29+2%5E1*%28h-2%29

因此有

eq?%28A*1+B%29*2%5E1-B%3D2%5E0*%28h-1%29

eq?%28A*2+B%29*2%5E2-B%3D2%5E0*%28h-1%29+2%5E1*%28h-2%29

两式子联立可得eq?A%3D-2%5E%7Bh-1%7D%2CB%3D-2%5Eh,eq?S_n的n为h-1

所以eq?T%28N%29%3D2%5Eh-h-1

又因为eq?N%3D2%5Eh-1,因此eq?h%5Capprox%20%5Clog_2%20%28N+1%29

最终结果

所以eq?T%28N%29%3DN-%5Clog_2%20%28N+1%29%20%5Capprox%20N

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

推导

设树高为h

39e01bdbb5cc491caf615aa7cf366d3d.png

发现如下规律

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

第1层,有eq?2%5E0个节点,最多向上调整1次

第2层,有eq?2%5E1个节点,最多向上调整2次

第3层,有eq?2%5E2个节点,最多向上调整3次

第4层,有eq?2%5E3个节点,最多向上调整4次

...

第h-1层,有eq?2%5E%7Bh-2%7D个节点,最多向上调整h-1次

第h层,有eq?2%5E%7Bh-1%7D个节点,最多向上调整h次

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

则有eq?T%28N%29%3D2%5E0*1+2%5E1*2+2%5E2*3+...+2%5E%7Bh-1%7D*%28h-1%29+2%5Eh*h

计算后有eq?T%28N%29%3D%28h-1%29*2%5E%7Bh+1%7D+2

又因为eq?N%3D2%5Eh-1,因此eq?h%5Capprox%20%5Clog_2%20%28N+1%29%5Capprox%20%5Clog_2%20N

最终结果

所以eq?T%28N%29%3D%28%5Clog_2%20%28N+1%29-1%29%28N+1%29*2+2%20%5Capprox%20N*%5Clog_2%20N

3.对比

时间复杂度对比

结论:向上调整的时间复杂度为eq?O%28N*%5Clog%20_2%20N%29,向下调整的时间复杂度为eq?O%28N%29

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

图像对比

cdb28fa4184447e0bb10c63d666b09b9.png

3cd032ce190a4322a838cf9de8b9c172.png 

显然随着x越来越大,eq?xeq?x*%5Clog_2%20x的差距会越来越大

4.练习题

题目

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

7cf7de489f934b16a3598f174753ea9f.png

 

分析

错误思路:因为while循环中有AdjustDown,所以为向下调整,时间复杂度为eq?O%28N%29

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

看二叉树的最后一层:有eq?2%5E%7Bh-1%7D个节点,每一个节点调整最多h次,因此属于eq?2%5E%7Bh-1%7D*h的求和计算,所以时间复杂度为eq?O%28N*%5Clog%20_2%20N%29

5.总结

用堆对数组进行排序,排升序建大堆的时间复杂度总为eq?O%28N*%5Clog%20_2%20N%29

对比

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)视作整体

 

 


网站公告

今日签到

点亮在社区的每一天
去签到