当前位置：首页 > article >正文

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

article 2024/11/30 3:45:21

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

推导

设树高为h

发现如下规律

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

第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_1$ 和 $eq?S_2$ 的值后再代入 $eq?S_n$ 中即可求出 $eq?A$ 和 $eq?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

发现如下规律

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

第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$

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

图像对比

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

4.练习题

题目

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

分析

错误思路:因为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)视作整体

查看全文

http://www.kler.cn/a/415091.html