分析速度和内存堆积

我试着用Google和wiki'ing这些问题，但似乎无法找到具体的答案。我发现的大部分内容都是用主定理证明的，但我希望能用更简单的方式记住那些简单英语的东西。此外，我不在学校，这些问题是面试。分析速度和内存堆积

MEMORY：

究竟是什么意思，以确定内存使用方面大O？例如，当你必须存储全部n个项目时，为什么认为heapsort与O（1）内存一起运行？是因为你只为堆创建了一个结构？还是因为你知道它的大小，所以你可以在堆栈上创建它，这总是不断的使用内存？

SPEED：

如何堆的创作O（n）的时间做，如果添加元素为O完成（1），但渗透在O（LOGN）做了什么？那不就是说你在O（1）处插入O（n），并在每个插入是O（logn）之后进行渗透。所以总共O（n）* O（logn）= O（nlogn）。我也注意到堆排序的大多数实现使用heapify函数而不是渗透来创建堆？由于heapify在O（logn）进行n次比较将会是O（nlogn），并且在n（O）的插入处我们会得到O（n）+ O（nlogn）= O（nlogn）？第一种方法不会比第二种方法产生更好的性能吗？

我有一种假设，但是这是真的，做O（1）操作n次会导致O（n）时间？或者n * O（1）= O（1）？

来源

2013-03-28 mpellegr

内存通常表示为O（1）*附加内存。即常量内存不计算被排序的对象本身。第二个问题[是重复]（http://stackoverflow.com/questions/9755721/build-heap-complexity）。 –

为什么是O（1）？您需要为堆中的所有n项分配内存，不应该是O（n）吗？ – mpellegr

请注意“附加”一词。项目本身的内存不计算为“额外”的一部分。想象一下，有人说：“这款车的售价为20,000美元，另外还有1000美元我们将增加GPS导航功能。”然后你说：“它怎么能只有2000美元？只是汽车本身花费2万美元！” 2000美元是*额外*费用;它不计算汽车本身的基本收费2万美元。同样，O（1）是* additional *内存使用情况，不包括项目本身的内存。 –

因此，我发现了一些关于从维基百科构建二进制堆的有用信息：http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap。

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

在保持heap属性的同时迭代添加项的方法在O（nlogn）中运行并创建堆而不考虑heap属性，然后heapifying，实际运行在O（n）中，原因不是很直观，需要证明，所以我错了。

获取订购商品的删除步骤在每个方法都有一个尊重heap属性的堆之后的成本O（nlogn）相同。因此，最终你可以为构建堆方法提供O（1）+ O（n）+ O（nlogn）= O（nlogn），并且O（nlogn）+ O（nlogn） = O（nlogn）为插入方法。显然，第一个是可取的，特别是对于小n。

来源

2013-03-28 16:05:48 mpellegr

分析速度和内存堆积

回答

相关问题