0

我尝试用谷歌搜索和维基搜索这些问题，但似乎找不到具体的答案。我发现的大部分内容都涉及使用主定理的证明，但我希望用简单的英语能更直观地记住一些东西。另外我不在学校，这些问题是为了面试。

记忆：

在内存使用方面确定 big-o 到底意味着什么？例如，当您必须存储所有 n 个项目时，为什么认为堆排序使用 O(1) 内存运行？是因为您只为堆创建一个结构吗？或者是因为你知道它的大小，所以你可以在堆栈上创建它，这始终是恒定的内存使用？

速度：

如果在 O(1) 中完成添加元素但在 O(logn) 中完成渗透，如何在 O(n) 时间内完成堆的创建？这是否意味着您在 O(1) 处进行 n 次插入，使其成为 O(n) 并在每次插入后渗透为 O(logn)。所以总共 O(n) * O(logn) = O(nlogn)。我还注意到堆排序的大多数实现都使用 heapify 函数而不是渗透来创建堆？由于 heapify 在 O(logn) 处进行 n 次比较，这将是 O(nlogn)，并且在 O(1) 处进行 n 次插入，我们将得到 O(n) + O(nlogn) = O(nlogn)？第一种方法在 n 较小的情况下不会比第二种方法产生更好的性能吗？

我在上面假设了这一点，但是执行 O(1) 操作 n 次是否会导致 O(n) 时间？还是 n * O(1) = O(1)？

4

1 回答 1

0

所以我从维基百科中找到了一些关于构建二进制堆的有用信息：http ://en.wikipedia.org/wiki/Binary_heap#Building_a_heap 。

我认为我的主要困惑来源是如何“插入”到堆中是 O(1) 和 O(logn)，即使第一个不应该被称为插入，也许只是一个构建步骤或其他东西。因此，在创建堆之后，您将不再使用 heapify，而是使用 O(logn) 插入方法。

在保持堆属性的同时迭代添加项的方法在 O(nlogn) 中运行，并且在不考虑堆属性的情况下创建堆，然后进行堆化，实际上在 O(n) 中运行，原因不是很直观，需要证明，所以我错了。

在每个方法都有一个尊重堆属性的堆之后，获取有序项的删除步骤是相同的​​成本，O(nlogn)。

所以最后你会有一个 O(1) + O(n) + O(nlogn) = O(nlogn) 用于构建堆方法，以及一个 O(nlogn) + O(nlogn) = O(nlogn ) 用于插入方法。显然第一个更可取，尤其是对于小的 n。

于 2013-03-28T16:05:48.143 回答