堆排序的速度和内存分析 [英] Analysis of speed and memory for heapsort

问题描述

我尝试使用谷歌搜索和Wiki'ing这些问题，但似乎找不到具体答案.我发现的大多数内容都涉及使用与主定理匹配的证明，但我希望可以用简单的英语来使事情更直观地被记住.我也不在学校，这些问题是要面试的.

I tried googling and wiki'ing these questions but can't seem to find concrete answers. Most of what I found involved using proofs with the master theorem, but I'm hoping for something in plain English that can be more intuitively remembered. Also I am not in school and these questions are for interviewing.

记忆力:

根据内存使用情况确定big-o到底意味着什么?例如，当必须存储所有n个项目时，为什么将为什么sortsort与O(1)内存一起运行?是因为您仅为堆创建一种结构吗?还是因为您知道它的大小，然后就可以在堆栈上创建它(始终保持不变的内存使用率)?

What exactly does it mean to determine big-o in terms of memory usage? For example, why is heapsort considered to run with O(1) memory when you have to store all n items? Is it because you are creating only one structure for the heap? Or is it because you know its size and so you can create it on the stack, which is always constant memory usage?

速度:

如果在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小吗?

How is the creation of the heap done in O(n) time if adding elements is done in O(1) but percolating is done in O(logn)? Wouldn't that mean you do n inserts at O(1) making it O(n) and percolating after each insert is O(logn). So O(n) * O(logn) = O(nlogn) in total. I also noticed most implementations of heap sort use a heapify function instead of percolating to create the heap? Since heapify does n comparisons at O(logn) that would be O(nlogn) and with n inserts at O(1) we would get O(n) + O(nlogn) = O(nlogn)? Wouldn't the first approach yield better performance than the second with small n?

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

I kind of assumed this above, but is it true that doing an O(1) operation n times would result in O(n) time? Or does n * O(1) = O(1)?

推荐答案

因此，我从Wikipedia中找到了一些有关构建二进制堆的有用信息:

So I found some useful info about building a binary heap from wikipedia: http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap.

我认为我的主要困惑是O(1)和O(logn)是如何插入"到堆中的，即使第一个不应被称为插入，也可能仅仅是构建步骤之类的东西.因此，在创建堆之后，就不再使用heapify，而是使用O(logn)插入方法.

I think my main source of confusion was how "inserting" into a heap is both O(1) and O(logn), even though the first shouldn't be called an insertion and maybe just a build step or something. So you wouldn't use heapify anymore after you've already created your heap, instead you'd use the O(logn) insertion method.

在维护堆属性的同时迭代添加项的方法在O(nlogn)中运行，而在不尊重堆属性的情况下创建堆，然后进行堆化的方法实际上在O(n)中运行，原因不是很直观并需要证明，所以我对此表示错误.

The method of adding items iteratively while maintaining the heap property runs in O(nlogn) and creating the heap without respecting the heap property, and then heapifying, actually runs in O(n), the reason which isn't very intuitive and requires a proof, so I was wrong about that.

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

The removal step to get the ordered items is the same cost, O(nlogn), after each method has a heap that respects the heap property.

因此，最后，对于构建堆方法，您将具有O(1)+ O(n)+ O(nlogn)= O(nlogn)，而O(nlogn)+ O(nlogn)=O(nlogn)用于插入方法.显然，第一个是可取的，特别是对于小n.

So in the end you'd have either an O(1) + O(n) + O(nlogn) = O(nlogn) for the build heap method, and an O(nlogn) + O(nlogn) = O(nlogn) for the insertion method. Obviously the first is preferable, especially for small n.

这篇关于堆排序的速度和内存分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！