免费手机建站网站,网站seo外链建设,微信推送在哪个网站做,大学生怎么做网站文章目录 前言一、堆排代码一、计算使用向上调整法建堆的时间复杂度二、计算使用向下调整法插入的时间复杂度总结 前言
在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好#xff0c;是因为使用向上调整法建堆的时间复杂… 文章目录 前言一、堆排代码一、计算使用向上调整法建堆的时间复杂度二、计算使用向下调整法插入的时间复杂度总结 前言
在博主的上一篇博客堆排(链接在这里点击即可)的总结中提出啦使用向下调整法建堆比使用向上调整法建堆更好是因为使用向上调整法建堆的时间复杂度为O(n*logn)使用向下调整法建堆的时间复杂度为O(n)。接下来博主就教大家如何计算它们的时间复杂度。 一、堆排代码
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
//向上调整法
void AdjustUp(HPDataType* arr, int child)
{int parent (child - 1) / 2;while (child 0)//不需要等于child只要走到根节点的位置根节点没有父节点不需要交换{if (arr[child] arr[parent])//若孩子结点比父结点小则交换{Swap(arr[parent], arr[child]);child parent;parent (child - 1) / 2;}else{break;}}
}
//向下调整法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child parent * 2 1;//左孩子while (child n){//找左右孩子中找最小的if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
//堆排
void HeapSort(int* arr, int n)
{//向上调整法建堆for (int i 0; i n; i){AdjustUp(arr, i);}//向下调整算法建堆//for (int i (n-1-1)/2; i 0; i--)//{// AdjustDown(arr, i , n);//}//循环将堆顶数据跟最后位置的数据进行交换int end n - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, 0, end);end--;}
}
一、计算使用向上调整法建堆的时间复杂度
for (int i 0; i n; i)
{AdjustUp(arr, i);
}第1层20个结点最多需要向上移动0次。第2层21个结点最多需要向下移动1次。第3层22个结点最多需要向上移动2次。…第h-1层2h-2个结点最多需要向上移动h-2次。第h层2h-1个结点最多需要向上移动h-1次。 所以最多移动的次数总和为 (1) T(h) 20(0)21(1)22(2)…2h-2(h-2)2h-1(h-1) (2) 2T(h) 21(0)22(1)23(2)…2h-1(h-2)2h(h-1) (2)-(1) 得 T(h) -(212223…2h-22h-12h-1)2hh 使用高中阶段学过的等比数列求和公式S a1(1-qn)/1-q可得 T(h) 2(1-2h)2hh 22h(h-2) 再根据二叉树的性质n 2h-1h log2(n1)可得 T(n) 2 (n1)(log2(n1)-2) (n1)log2(n1)-2n 所以向上调整法建堆的时间复杂度为O(logn*n) 二、计算使用向下调整法插入的时间复杂度
for (int i (n-1-1)/2; i 0; i--)
{AdjustDown(arr, i , n);
}第1层20个结点最多需要向下移动h-1次。第2层21个结点最多需要向下移动h-2次。第3层22个结点最多需要向下移动h-3次。…第h-1层2h-2个结点最多需要向下移动1次。第h层2h-1个结点最多需要向下移动0次。 所以最多移动的次数总和为 (1) T(h) 20(h-1)21(h-2)22(h-3)…2h-2(1) (2) 2T(h) 21(h-1)22(h-2)23(h-3)…2h-1(1) (2)-(1) 得 T(h) 212223…2h-22h-1-20(h-1) T(h) 20 212223…2h-22h-1-h 使用高中阶段学过的等比数列求和公式S a1(1-qn)/1-q可得 T(h) 2h-1-h 再根据满二叉树的性质n 2h-1h log2(n1)可得 T(n) n-log2(n1)* 所以向下调整法建堆的时间复杂度为O(n) 总结
通过这篇博客相信柚柚们已经清楚向下调整法建堆和向上调整法建堆的时间复杂度怎么计算啦后期博主还会更新有关数据结构的博客感兴趣的柚柚们可以关注博主喔~
