分析速度和內存堆積

我試着用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

分析速度和內存堆積

回答

相關問題