保持排序列表的複雜性vs插入所有值然後排序

將時間和空間的複雜性保持在排序順序中的數字列表（即從第一個插入它，第二個來你插入它按排序順序等等..）與插入它們時相同，然後在所有插入完成後進行排序？保持排序列表的複雜性vs插入所有值然後排序

我該如何做出這個決定？你能用'n'元素的時間和空間複雜性來證明嗎？

我一直在考慮電話簿，將它存儲在一個集合中，並在用戶每次向電話簿中插入記錄時按順序將數據呈現給用戶，VS按照排序順序將電話簿記錄存儲在樹中。 n元素會是什麼？

來源

2013-06-24 Phoenix

n，是不是對事物進行計數，它只能將算法與稱爲O（1）的最佳解決方案區分開來。這個概念並不像理解那麼簡單，所以花點時間去理解它。 Upvote，繼續。我相信你會喜歡這種學習。 – Siddharth

含糊不清的標題將不會對將來訪問該網站的用戶造成同樣的問題。 –

將會有特定於應用程序的折衷選擇算法。在Insertion Sort維基百科頁面上列舉了可能使用插入排序而不是某種離線排序算法的原因。

這裏的決定因素是不太可能是漸進的複雜性，更可能是你知道你的數據是什麼（比如，是不是有可能被已經排序？）

我會走得更遠，但我我不相信這不是一個逐字問我的作業問題。

來源

2013-06-24 04:56:54 Gian

是反對意見表達的分歧嗎？ – Gian

這就是我，這是因爲插入，然後排序不是'O（n^2）'最壞的情況。 –

@PhilipJF，我說的是quicksort，在'average（平均）'情況下是'O（n log n）'，最糟糕的情況是'O（n^2）'。合併排序或其他與'O（n log n）'最差的情況將會有額外的空間要求。 – Gian

這取決於你將數據結構插入到哪個數據結構中。如果你問的是插入數組，那麼答案是否定的。它需要O（n）空間和時間來存儲n個元素，然後O（n log n）對它們進行排序，所以O（n log n）總和。插入數組可能需要移動\ Omega（n）元素，因此需要\ Theta（n^2）。大多數「順序」數據結構也會出現同樣的問題。抱歉。另一方面，諸如懶惰左堆，斐波那契堆和Brodal隊列等優先級隊列具有O（1）插入。雖然，一個手指樹給O（n log n）插入和線性訪問（手指樹和鏈表一樣好，鏈表對於什麼是好的，和平衡二叉搜索樹一樣好，因爲二叉搜索樹對於什麼是好的 - 他們真是太棒了）。

來源

2013-06-24 04:57:18

每次插入一個排序列表並保持它的排序，就是O（logn）比較來找到放置它的位置，但是O（n）移動來放置它。由於我們插入n個元素，所以這是O（n^2）。但是，我認爲如果你使用的數據結構是爲了插入排序後的數據而設計的（比如二叉樹），那麼在結尾做一個傳遞來把它變成一個列表/數組，它只是O（nlogn）。另一方面，使用這種更復雜的數據結構將使用大約O（n）個額外的空間，而所有其他方法可以在原地完成並且不使用額外的空間。

每次插入未排序列表時，都是O（1）。最後將它排序爲O（nlogn）。這意味着總體上它是O（nlogn）。然而，如果你不打算列出許多元素（1000或更少），那它可能並不重要，它應該關注什麼對於小數據集運行得更快，或者如果不是性能問題，不用擔心。

來源

2013-06-24 04:57:31 Patashu

是否收回downvote'O（n^2logn）'是一個相當奇怪的構造。由於'n'趨於無窮大，因此'n^2'項遠遠大於'log n'，所以這相當於只寫'O（n^2）'（這恰好是已知的最壞情況）插入排序）。 – Gian

@Gian這就是我的直覺告訴我的，但爲什麼O（nlogn）值得與O（n）區分呢？ – Patashu

因爲Big-O符號實際上就是對函數的增長率進行分類 - 在這種情況下，「n * log n」比'O（n）'增長得快得多（特別是當'n'趨於無窮大時，這是關於Big-O符號的其他重要部分）。 – Gian

-1

選項1

插入在有序正確的位置。採取

時間找到位置爲第i + 1個元素：O(logi)

插入和用於維持秩序採取時刻i + 1個元素：O(i)

空間複雜度：O(N)

總時間：(1*log 1 +2*log 2 + .. +(N-1)*logN-1) = O(NlogN)

瞭解這只是時間複雜性。運行時間可能與此非常不同。

選項2：

插入件O(1)

排序元素O(NlogN)

根據你使用的排序空間複雜度各不相同，雖然你可以使用像快速排序，這不反正需要很多空間。

總之雖然時間複雜度都是一樣的，但邊界很薄弱，在數學上你可以想出更好的邊界。還要注意在實際情況下可能永遠不會遇到最壞情況的複雜度，可能你只會看到平均情況全部時間。如果性能在你的應用程序中是如此重要的問題，你應該隨機抽樣測試這兩套代碼。請告訴我哪個測試後工作得更快。我猜是選項1.

來源

2013-06-24 06:37:32 Aravind

保持排序列表的複雜性vs插入所有值然後排序

回答

相關問題