不推公式,形象理解堆排序的时间复杂度

简介: 不推公式,形象理解堆排序的时间复杂度

我们首先要明晰几点:1,算堆排序的时间复杂度算的是交换次数而不是比较次数。2,设数据个数为N,高度便为lg N。3,为了推算最坏情况,我们用满二叉树,并且N无限大, lg N也无限大




建堆的时间复杂度

为了追求效率,一般选用向下调整建堆。从倒数第二层的最后一个节点开始向下调整,这一层一共有1/4N个节点,最坏情况下每个节点都要向下调整一次,这一层最坏调整1/4N次,倒数第三层有1/8N个节点,最坏情况下每个节点都要向下调整两次,所以倒数第三层最坏要调整1/4N次,倒数第四层有1/16N个节点,最坏情况下每个节点都要向下调整3次,所以倒数第四层最坏情况最坏要调整3/16N次,这三层已经接近3/4N次了,一次往后推,整个向下调整建堆的交换次数接近N次,所以建堆的时间复杂度在O(N)这个量级。

                                       

                                                排序的时间复杂度

排序时会让第一个数据和最后一个数据交换,让最后一个数据在第一个数据的位置向下调,直到符合堆的排列规则为止,然后总数减一。最后一层有1/2N个数据,最坏情况下,每个数据都要和第一个数据较换并且向下调整,而下调最坏情况是高度次减一,也就是lg N - 1,因为lg N特别大, lg N  ==

lg N - 1。所以最后一层最坏情况是交换1/2N * lg N次,倒数第二层也同理,lg N - 2 == lg N,倒数第三层也同理。所以整体的交换次数是趋近于 N * lg N的,所以排序的时间复杂度在N * lg N这个量级。

                                   

堆排序的时间复杂度

把上述的时间复杂度相加的  N + N * lg N  == N(1  +   lg N),由于lg N 特别大,1可以忽略不计, 所以堆排序的时间复杂度在 N * lg N这个量级。

相关文章
|
算法 测试技术
较难算法美丽塔时间复杂度O(nlogn)
较难算法美丽塔时间复杂度O(nlogn)
|
1月前
|
算法 开发者
【时间复杂度和空间复杂度之间的故事】
【时间复杂度和空间复杂度之间的故事】
18 5
|
6月前
|
算法 数据处理 C语言
【数据结构与算法】快速排序(详解:快排的Hoare原版,挖坑法和双指针法|避免快排最坏时间复杂度的两种解决方案|小区间优化|非递归的快排)
【数据结构与算法】快速排序(详解:快排的Hoare原版,挖坑法和双指针法|避免快排最坏时间复杂度的两种解决方案|小区间优化|非递归的快排)
|
6月前
|
存储 算法
何为时间复杂度和空间复杂度
何为时间复杂度和空间复杂度
29 1
|
6月前
|
算法
时间复杂度与空间复杂度(自漫画算法)
时间复杂度与空间复杂度(自漫画算法)
31 0
|
6月前
|
机器学习/深度学习 算法 搜索推荐
【算法训练-排序算法 一】【手撕排序】快速排序、堆排序、归并排序
【算法训练-排序算法 一】【手撕排序】快速排序、堆排序、归并排序
84 0
|
11月前
|
搜索推荐 算法
手撕排序算法2:堆排序和直接选择排序(下)
手撕排序算法2:堆排序和直接选择排序(下)
|
11月前
|
搜索推荐 算法 C语言
手撕排序算法5:快速排序非递归版本和计数排序
手撕排序算法5:快速排序非递归版本和计数排序
|
11月前
|
算法 搜索推荐 测试技术
手撕排序算法2:堆排序和直接选择排序(上)
手撕排序算法2:堆排序和直接选择排序(上)
|
算法 搜索推荐 测试技术
【数据结构】 七大排序详解(壹)——直接插入排序、希尔排序、选择排序、堆排序
【数据结构】 七大排序详解(壹)——直接插入排序、希尔排序、选择排序、堆排序