知识卡片
自底向上建堆是线性时间
底层节点数量多但高度小,上层节点数量少而高度大;将各层节点数乘以其最大下沉距离求和,可得自底向上建堆 O(n),而不是把每次调用都按堆的最大高度计费。随后 n−1 次取最大与下沉的总最坏时间为 O(n log n)。
零基实现对 n≥2 调用 ⌊n/2⌋ 次建堆下沉;书中把调用次数写成 ⌊n/2⌋−1,且将调用次数乘对数称作堆深度,均不准确。完全二叉树的高度是 O(log n)。
91的03216–03217表比较递归与非递归实现,在给定平台和随机测试下数值接近;实际差异应在目标环境测量,两者渐近上界相同。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 自底向上建堆是线性时间
- · 变种
原书出处 · 2 处
- · 查看原书依据
分析 堆排序的核心函数是heapify。在buildHeap中,这个函数将会被调用n/2」-1次,在实际排序中,它也会被调用n-1次,总共调用了3*n/2」-2次。如你所见,这是一个递归的操作,在到达堆的底部之前会执行固定数目的计算。因为形状的性质,堆的深度将会是(3*n/2」-2)*log(n)」
- · 查看原书依据
非递归的堆排序实现,表4-4列出了对两种实现执行1000个随机测试的结果,抛弃了最好和最坏的结果。剩余结果的平均值如表4-4所示。
参考来源
- 位置:《算法技术手册》第4章《分析》(spine1516;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1479.html;u090-ch04-021)。
- 结论依据:90全文、03185符号及03215循环实读;计数和分层求和为推导。
- 原始内容:分析 堆排序的核心函数是heapify。在buildHeap中,这个函数将会被调用n/2」-1次,在实际排序中,它也会被调用n-1次,总共调用了3*n/2」-2次。如你所见,这是一个递归的操作,在到达堆的底部之前会执行固定数目的计算。因为形状的性质,堆的深度将会是(3*n/2」-2)*log(n)」
- 位置:《算法技术手册》第4章《变种》(spine1517;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1480.html;u091-ch04-021)。
- 结论依据:91的03216–03217表比较递归与非递归实现,在给定平台和随机测试下数值接近;实际差异应在目标环境测量,两者渐近上界相同。
- 原始内容:非递归的堆排序实现,表4-4列出了对两种实现执行1000个随机测试的结果,抛弃了最好和最坏的结果。剩余结果的平均值如表4-4所示。