3

当我在大学学习数据结构课程时，我学到了以下公理：

  1. 在最坏的情况下，向堆中插入一个新数字需要O(logn)（取决于作为叶子插入时它在树中到达的高度）

  2. 从一个空堆开始，使用n次插入，构建一个包含n 个节点的堆，使用分期分析将总和到O(n)时间

  3. 在最坏的情况下，移除最小值需要O(logn)时间（取决于新顶部节点在与最后一个叶子交换后达到的低点）

  4. 一个一个地去除所有最小值，直到堆为空，需要O(nlogn)时间复杂度


提醒： “堆排序”算法的步骤是：

  • 将所有数组值添加到堆中：使用摊销分析技巧求和到O(n)时间复杂度
  • 从堆中弹出最小值n次并将第i个值放在数组的第i个索引中：O(nlogn) 时间复杂度，因为在弹出最小值时摊销分析技巧不起作用

我的问题是：为什么在清空堆时摊销分析技巧不起作用，导致堆排序算法花费O(nlogn)时间而不是O(n)时间？

编辑/回答

当堆存储在一个数组中（而不是带有指针的动态树节点）时，我们可以自底向上构建堆，即从叶子开始到根，然后使用摊销分析我们可以得到总时间复杂度的O(n)，而我们不能清空堆最小值的自下而上。

4

2 回答 2

1

假设您只允许通过比较两个对象来了解它们的相对排名，那么就无法在 O(n) 时间内将所有元素从二叉堆中出列。如果你能做到这一点，那么你可以在 O(n) 时间内对列表进行排序，方法是在 O(n) 时间内构建一个堆，然后在 O(n) 时间内将所有内容出队。但是，排序下限表示比较排序为了正确，平均必须具有 Ω(n log n) 的运行时间。换句话说，你不能太快地从堆中出列，否则你会打破排序障碍。

还有一个问题是为什么从二进制堆中取出 n 个元素需要时间 O(n log n) 而不是更快。这有点难以展示，但这是基本的想法。考虑您在堆上进行的出列队列的前半部分。查看实际出队的值，并考虑它们在堆中的位置。除了最底行的那些之外，其他所有出队的东西都必须一次一次地渗透到堆的顶部才能被删除。您可以证明堆中有足够的元素来保证仅此一项就需要时间 Ω(n log n)，因为这些节点中大约有一半将位于树的深处。这解释了为什么摊销参数不起作用 - 您不断地将深层节点拉到堆上，因此节点必须移动的总距离很大。

于 2015-08-20T17:11:37.843 回答
1

让我“以数学方式”向您展示我们如何计算将任意数组转换为堆（让我称之为“堆构建”）然后使用堆排序对其进行排序的复杂性。

堆构建时间分析

为了将数组转换为堆，我们必须查看每个具有子节点的节点并“堆”（接收）该节点。您应该问问自己我们进行了多少次比较；如果你仔细想想，你会看到（h = 树高）：

  • 对于第 i 层的每个节点，我们进行 hi 比较：#comparesOneNode(i) = hi
  • 在第 i 层，我们有 2^i 个节点：#nodes(i) = 2^i
  • 因此，通常 T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i *(hi)，是在“i”级别“比较”所花费的时间

让我们举个例子。假设有一个包含 15 个元素的数组，即树的高度为 h = log2(15) = 3：

  • 在级别 i=3，我们有 2^3=8 个节点，我们对每个节点进行 3-3 次比较：正确，因为在级别 3 我们只有没有子节点的节点，即叶子。T(n, 3) = 2^3*(3-3) = 0
  • 在 i=2 级别，我们有 2^2=4 个节点，我们对每个节点进行 3-2 次比较：正确，因为在级别 2 我们只有级别 3 可以与之比较。T(n, 2) = 2^2*(3-2) = 4 * 1
  • 在 i=1 级别，我们有 2^1=2 个节点，我们对每个节点进行 3-1 次比较：T(n, 1) = 2^1*(3-1) = 2 * 2
  • 在 i=0 级别，我们有 2^0=1 个节点，即根节点，我们进行 3-0 次比较：T(n, 0) = 2^0*(3-0) = 1 * 3

好的，一般来说：

T(n) = sum(i=0 to h) 2^i * (hi)

但如果你记得 h = log2(n)，我们有

T(n) = sum(i=0 to log2(n)) 2^i * (log2(n) - i) =~ 2n

堆排序时间分析

现在，这里的分析非常相似。每次我们“删除”最大元素（根）时，我们都会移动到树中最后一个叶子的根，将它堆起来并重复直到最后。那么，我们在这里执行多少比较？

  • 在第 i 层，我们有 2^i 个节点：#nodes(i) = 2^i
  • 对于级别“i”的每个节点，heapify，在最坏的情况下，将始终执行与级别“i”完全相同的比较次数（我们从级别 i 中取出一个节点，将其移动到根，调用 heapify ，并且在最坏的情况下 heapify 会将节点带回级别 i，执行“i”比较）：#comparesOneNode(i) = i
  • 因此，通常 T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i*i 是移除前 2^i 个根并将临时根带回正确位置所花费的时间.

让我们举个例子。假设有一个包含 15 个元素的数组，即树的高度为 h = log2(15) = 3：

  • 在 i=3 级别，我们有 2^3=8 个节点，我们需要将每个节点移动到根位置，然后将每个节点堆起来。每个 heapify 将在最坏的情况下执行“i”比较，因为根可能会下降到仍然存在的级别“i”。T(n, 3) = 2^3 * 3 = 8*3
  • 在 i=2 级别，我们有 2^2=4 个节点，我们对每个节点进行 2 次比较：T(n, 2) = 2^2*2 = 4 * 2
  • 在 i=1 级别，我们有 2^1=2 个节点，我们对每个节点进行 1 次比较：T(n, 1) = 2^1*1 = 2 * 1
  • 在 i=0 级别，我们有 2^0=1 个节点，即根节点，我们进行 0 次比较：T(n, 0) = 0

好的，一般来说：

T(n) = sum(i=0 to h) 2^i * i

但如果你记得 h = log2(n)，我们有

T(n) = sum(i=0 to log2(n)) 2^i * i =~ 2nlogn

堆构建 VS 堆排序

直观地，您可以看到堆排序无法“摊销”他的成本，因为每次我们增加节点数量时，我们必须做更多的比较，而堆构建功能恰恰相反！你可以在这里看到：

  • 堆构建：T(n, i) ~ 2^i * (hi)，如果 i 增加，#nodes 增加，但 #compares 减少
  • 堆排序：T(n, i) ~ 2^i * i，如果i增加，#nodes增加，#compares增加

所以：

  • 级别 i=3，#nodes(3)=8，堆构建进行 0 次比较，堆排序进行 8*3 = 24 次比较
  • 级别 i=2，#nodes(2)=4，堆构建进行 4 次比较，堆排序进行 4*2 = 8 次比较
  • 级别 i=1，#nodes(1)=2，堆构建进行 4 次比较，堆排序进行 2*1 = 2 次比较
  • 级别 i=0，#nodes(0)=1，堆构建进行 3 次比较，堆排序进行 1*0 = 1 次比较
于 2020-12-26T17:11:29.280 回答