我想了解大哦表示法。任何幫助，將不勝感激。解決：大哦表示法堆
說有是創建一個最大堆，然後推動並刪除項目的程序。
說有n個項目。
要創建堆，它需要O（n）與heapify如果已讀入到一個數組，然後，它heapifies。 爲推動的物品，它需要O（1）和將其刪除，需要O（1） 要之後heapify它，它以對數n，用於每個刪除和n日誌n，用於n個項
所以大哦表示法是O（n + n log n） 或者，它是O（n log n），只是因爲我們選擇了最大的一個。
在堆中堆積新元素的複雜性爲O(logN)，而不是O(1)（除非使用看起來不是這樣的Fibonacci heap）。
也沒有符號O(N + NlogN)爲NlogN增長快於N所以這個符號簡單標記爲O(NlogN)。
編輯：大哦符號只說明一個函數的漸近行爲，那就是 - 它的增長速度。當你接近無窮大2*f(x)和11021392103*f(x)行爲相似，這就是爲什麼當寫大哦表示法時，我們忽略在函數前面的任何常量。
對不起，您提到「只考慮取決於輸入大小的術語」。說，這n是某種程度上涉及，你的意思是n（nlog n）罰款 – user1952529
@ user1952529對不起，我不明白什麼評論的意思。 –
非常感謝您查看此..我很困惑，當我應該添加常量到大哦表示法。 perreal提到只考慮依賴於輸入大小的術語。這是什麼意思？ – user1952529
從形式上來講，O(N + N log N)相當於O(N log N)。
這就是說，它假定有係數埋藏在每一個這些，鼻翼：O(aN + bN log(cN))。如果您有非常大N值，這些係數變得不重要，算法僅通過其規模最大的一屆，其中，在這種情況下，爲log(N)界。
不過，這並不意味着這些係數爲完全不重要。這就是爲什麼在圖形算法的討論中，你會經常看到作者說「類似於Floyd-Warshall algorithm在O（N^3）時間運行，但是具有小系數」。
如果我們能夠以某種方式寫在這種情況下，O（0.5N^3），我們會。但事實證明，這些係數取決於你如何實現一個算法和你運行它的計算機。因此，我們決定進行漸近比較，不一定是因爲它是最好的方式，而是因爲沒有一個很好的選擇。
您還會看到喜歡的東西 「最壞情況：O（N^2），平均情況：O（N）」。這是試圖捕捉算法的行爲如何隨着輸入而變化。通常情況下，預先排序或隨機輸入可以給你這種平均情況，而邪惡的惡棍可以構造產生最壞情況的輸入。
最終，我的意思是這樣的：O(N + N log N)=O(N log N)。這是真的，這是你作業的正確答案。但我們用這個大O符號進行溝通，並在適當的時候，你會發現，你覺得O(N + N log N)更有表現，也許如果你的算法，一般用於小N情況。在這種情況下，不要太擔心形式主義 - 只要清楚你想要傳達的是什麼。
'O（n + n log n）= O（n log n）' – perreal
從你的答案中，我明白你總是拿最大的。 – user1952529
是的，你只考慮占主導地位的術語 – perreal