自底向上堆分析

Question

我正在尝试对自下而上的堆分析进行时间复杂度分析，但我被卡住了。我已经完成了数学评估，表明它是 O(n)，我完全理解为什么。我无法理解的部分是 "code" 它是如何实现这一点的。我知道外部 for 执行 floor(n/2) 次，我相信 while 执行 log 次，但我不知道如何从 floor(n/2)log 到 O(n)。

伪代码：时间分析：

for i = n/2-1; i <=0; i--         n/2+1
  k=i                             n/2
  while(2*k-1 <= n)               n/2(????)+1  <-- this is where I'm stuck. Should run log n times?
    j = k*2-1                     ...
    if(j<n && H[j] < H[j+1])      ...
      j++                         ...
    if(H[k] < h[j])               ...
      break                       ...
    swap(H[k],H[j])               ...
    k=j                           ...

所以我可以看到 while 可能运行 log n 次，但我看不到如何从那里 (n/2)log n 到 O(n)。我只是在寻找最坏的情况，因为我知道最好的情况是 n/2 + 1 因为当子树是堆时它会中断。欢迎任何帮助或指导阅读 material。

Answer 1

关于计算不同循环的大 O 成本，我必须提供的最佳建议是：

"When in doubt, work inside out!"

换句话说，不是从最外层循环开始向内工作，而是从最内层循环开始向外工作。

在这种情况下，我们有以下代码：

for i = n/2-1; i >= 0; i--
  k=i                           
  while (2*k-1 <= n)
    j = k*2-1
    if(j<n && H[j] < H[j+1])
      j++
    if(H[k] < h[j])
      break
    swap(H[k],H[j])
    k=j

由于我们正在从里到外工作，让我们首先关注这个循环：我们先从最里面的循环开始分析：

  while (2*k-1 <= n)
    j = k*2-1
    if(j<n && H[j] < H[j+1])
      j++
    if(H[k] < h[j])
      break
    swap(H[k],H[j])
    k=j

我假设这是最坏情况分析，我们永远不会触发内部 break 语句。在那种情况下，这意味着循环通过在循环的每个步骤之后让 k 移动到 2k - 1 或 2k 来进行。这意味着 k 在循环的每次迭代中大致翻倍。当k超过n时循环结束，所以循环的迭代次数等于在k超过[=20之前我们必须加倍k的次数=].这对 O(log(n / k)) 总循环迭代有效。请注意，这不是常数；随着 k 变小，我们最终每次迭代做的工作越来越多。

我们可以用更简单的“做 O(log(n / k)) 工作”替换内部循环来得到这个：

for i = n/2-1; i >= 0; i--
  k=i                           
  do O(log (n / k)) work;

并且，由于 k = i，我们可以将其重写为

for i = n/2-1; i >= 0; i--
  do O(log (n / i)) work;

现在，这里总共完成了多少工作？将所有迭代中每次迭代完成的工作相加，我们得到完成的工作是

log (n / (n/2)) + log (n / (n/2 - 1)) + log (n / (n/2 - 2)) + ... + log(n / 2) + log(n / 1).

现在，我们“所有”要做的就是简化这个总和。 :-)

利用对数的性质，我们可以将其重写为

(log n - log (n/2)) + (log n - log(n/2 - 1)) + (log n - log(n/2 - 2)) + ... + (log n - log 1)

= (log n + log n + ... + log n) - (log(n/2) + (log(n/2 - 1) + ... + log 1)

= (n/2)(log n) - log((n/2)(n/2 - 1)(n/2 - 2) ... 1)

= (n/2)(log n) - log((n/2)!)

现在，我们可以使用Stirling's approximation重写

log((n/2)!) = (n/2)log(n/2) - n log e + O(log n)

因此，要得到这个：

(n/2)(log n) - log((n/2)!)

= (n/2)(log n) - (n/2)log(n/2) + n log e - O(log n)

= (n/2)(log (2n / 2)) - (n/2) log (n/2) + O(n)

= (n/2)(log 2 + log(n/2)) - (n/2) log (n/2) + O(n)

= (n/2)(1 + log(n/2)) - (n/2) log (n/2) + O(n)

= n/2 + O(n)

= O(n).

所以这个总和等于 O(n).

如您所见，这是一个非常重要的大 O 计算！事实上，这比仅计算每次迭代完成的工作并乘以迭代次数要棘手得多，因为每次迭代的工作在迭代之间变化的方式使得这更难做到。相反，我们必须对每个循环完成多少工作进行更细致的分析，然后将事情转换为求和并提出一些重要的（尽管并非完全出乎意料的）技巧（斯特林的近似和对数的性质）来获得一切按预期锻炼。

我会将这组特定的循环归类为一个相当棘手的循环，并且不能特别代表您在进行循环分析时“通常”看到的内容。但希望这里的技术能让您了解如何通过更棘手的循环分析进行工作，并瞥见其中的一些美丽数学。

希望对您有所帮助！

自底向上堆分析

Bottom up heap analysis

algorithm

heap

big-o

time-complexity

heapsort