堆排序中建堆过程时间复杂度O(n)怎么来的?
2024-10-12 03:39:20
首先这个循环是从i = headsize/2 -> 1,也就是说这是一个bottom-up的建堆。于是,有1/2的元素向下比较了一次,有1/4的向下比较了两次,1/8的,向下比较了3次,......,1/2^k的向下比较了k次,其中1/2^k <= 1, k 约等于lg(n)。于是就有总的比较量:
T = () * n
令 S =
1/2 S =
S - 1/2S = 1/2S =
到这步就很明显了吧,S <= 2
于是T <= 2n => T = O(n).
最新文章
- sql server 更新视图的sp
- NashZhou的自我介绍
- 1025关于explain的补充1
- Hadoop入门进阶课程9--Mahout介绍、安装与应用案例
- MySQL创建数据表
- Codeforces Round #104 (Div. 1)
- hadoop2.5.2学习及实践笔记(二)—— 编译源代码及导入源码至eclipse
- oracle merge用法
- Oracle 12c Dataguard 数据库恢复
- 在VS中让一个JS文件智能提示另一个JS文件中的成员
- (转载)研究openvswitch的流量模式
- Windows 下多线程编程技术
- ViewFilpper
- ALV编辑行内容有改变时候操作
- JS的组成部分、引入页面的方法以及命名规范
- js 数组的一些基本操作
- Evensgn 剪树枝 树规
- Dapp的PVP发模式--magic-maze-2d游戏解读
- PostGIS空间查询
- ETL面试题集锦