下面是建立大根堆的代码
template <typename Type>
void CreateBigRootHeap(Type *array, int len)
{
int i, j, k;
Type temp;
for (i = (len - 1) / 2; i >= 0; --i)
{
temp = array[i];
k = i;
for (j = i * 2 + 1; j < len; j = j * 2 + 1)
{
if (j < len - 1 && array[j] < array[j + 1])
j += 1;
if (temp > array[j])
break;
array[k] = array[j];
k = j;
}
array[k] = temp;
}
}
现在对建立堆时所使用的时间复杂度为O(n)进行证明:
令堆所对应的完全二叉树的高度为h,节点的个数为n,现假定完全二叉树为满二叉树:即n = 2^h - 1,如下图(借用网上的图)所示
有2^(h-2)个结点向下访问一次,2^(h-3)个结点向下访问2次,...1个结点向下访问h次:
推导公式如下:
在堆所对应的二叉树为非满二叉树时,复杂度是n同阶的。
Apr 16, 2013 @lab
分享到:
相关推荐
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
对若干个数据进行操作,实现快速排序、选择排序、直接插入排序、堆排序算法时间复杂度的比较;并在排序数据中快速查找某一数据,给出查找是否成功,以及数据所在的位置信息。
以堆排序算法为例,改变输入规模n,测试算法时间复杂度
改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析改进的堆排序算法及其复杂度分析
排序(Sorting) 是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的...本文主要介绍快速排序算法和归并排序算法的基本概念、原理以及具体的实现方法,并对这两种排序算法的时间复杂度进行分析。
两个重要的排序算法的时间复杂度比较。所用的代码比较简陋,使用控制台。
直接是C程序 冒泡排序与合并排序的时间复杂度比较
C/C++排序算法 计时 时间复杂度分析
各种排序算法的稳定性和时间复杂度总结。希望大家能有所收获。
对java的8种排序方法的空间复杂度和时间复杂度,进行了一个简单的统计
使用插入、冒泡、选择、快排、归并、堆排共6种排序算法对同一序列进行排序,统计排序所需的平均时间并比较算法在时间上的优劣。供学习使用。
直接插入排序的时间复杂度为O(n^2),其中n是待排序元素的数量。这是因为对于每个待插入元素,都需要进行至多n-1次比较。直接插入排序的空间复杂度为O(1),因为它不需要额外的存储空间。此外,直接插入排序是稳定的,...
各种排序算法的稳定性和时间复杂度小结,包含各种排序算法,对找工作,做项目都有帮助
最好情况下, 最坏情况下, 平均情况下的时间复杂度
博客《数据结构与算法 —— 排序算法(3)》中的桶排序的时间复杂度计算公式推到过程。
改文件为排序算法、时间对比及时间复杂度直线拟合的源码,稍微加以修改即可在自己的代码中用于使用!
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
排序算法时间复杂度的研究 期刊网站可是要现金的哦。