知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.20 · 生成模型:未记录

自底向上建堆是线性时间

理解等级:中级

底层节点数量多但高度小,上层节点数量少而高度大;将各层节点数乘以其最大下沉距离求和,可得自底向上建堆 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所示。