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

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

我们首先要明晰几点: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):通过简单的排序算法来认识时间复杂度
初阶算法(1):通过简单的排序算法来认识时间复杂度
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
27 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
1月前
|
算法 开发者
【时间复杂度和空间复杂度之间的故事】
【时间复杂度和空间复杂度之间的故事】
21 5
|
5月前
|
人工智能 算法 C语言
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
数据结构与算法——简单排序-冒泡排序、插入排序,时间复杂度下界(图示、代码、时间复杂度、定理)
36 0
|
6月前
|
存储 算法
何为时间复杂度和空间复杂度
何为时间复杂度和空间复杂度
35 1
|
6月前
|
算法 搜索推荐 Java
数据结构与算法面试:基于比较的排序算法时间复杂度最坏情况下是 O(nlogn),请问有没有更快的算法?(提示:计数排序、基数排序)
数据结构与算法面试:基于比较的排序算法时间复杂度最坏情况下是 O(nlogn),请问有没有更快的算法?(提示:计数排序、基数排序)
48 0
|
6月前
|
算法
时间复杂度与空间复杂度(自漫画算法)
时间复杂度与空间复杂度(自漫画算法)
33 0
|
6月前
|
机器学习/深度学习 算法 搜索推荐
【算法训练-排序算法 一】【手撕排序】快速排序、堆排序、归并排序
【算法训练-排序算法 一】【手撕排序】快速排序、堆排序、归并排序
85 0
|
11月前
|
搜索推荐 算法
手撕排序算法2:堆排序和直接选择排序(下)
手撕排序算法2:堆排序和直接选择排序(下)