我應該選擇高時間複雜度數據結構還是高空間複雜度數據結構以獲得有效的方法？

我必須在兩個數據結構ArrayList和LinkedList之間進行選擇。我有兩個操作op_one，op_two。我應該選擇高時間複雜度數據結構還是高空間複雜度數據結構以獲得有效的方法？

如果讓我選擇的ArrayList - 我將結束與

for op_one ------ O(n), and at maximum n re-allocations 
for op_two ------ O(1), and at maximum n re-allocations

如果讓我選擇的LinkedList - 我將結束與

for op_one ------ O(n), and zero re-allocations 
for op_two ------ O(n), and zero re-allocations

我將存儲數百萬可比元素。我將同樣做這兩種操作。我應該選擇哪一個。

來源

2012-09-08 Sravan

我明白你指望重新分配內存複雜度（刪除或插入一個項目時，在一個陣列轉移項目），但重分配是時間複雜性。因此，ArrayList的op_two可能是O（n）和** not ** O（1）。不知怎的，我理解了關於哪個時間複雜度更好/更差的問題 – Javier

此外，如果每個重新分配意味着移動N個項目。 N重新分配意味着O（N^2）時間複雜度。請澄清一下。 – Javier

是否可以讓操作創建List？ – Tom

（問題首先理解爲時間複雜度無視空間。請求澄清在意見中提出）

我會使用ArrayList（超過鏈表），不僅因爲時間複雜度，但因爲它更簡單，它不爲每個項目建立一個新節點。在任何情況下，注意總體複雜度將爲O（n）：對於ArrayList，O（n）+ O（1）或者prob * O（n）+（1-prob）* O（1）將是按照O（n）的順序。給定相等的複雜度（O（n）），那麼你應該找出實際的執行時間，或選擇更容易實現或維護。

來源

2012-09-08 07:33:01 Javier

我想你的意思是ArrayList不會爲每個項目建立一個新的節點。 –

@PeterLawrey你是對的：更正。 – Javier

我建議你把它們放在一起並以現實的方式來看看哪個更快。如果他們沒有顯着差異，我會用你認爲最簡單的方法。

雖然ArrayList和LinkedLIst的順序對於空間是相同的，但ArrayList要小得多。

除非您知道您遇到性能問題，否則所有相同的清晰度通常都是最重要的。

來源

2012-09-08 07:36:35

考慮到在現代架構中內存帶寬往往是瓶頸。有時計算結果比存儲和讀取預先計算的值更快。換句話說，計算複雜性應與存儲器複雜性一起考慮。如果計算不昂貴並且可以在緩存內工作，我會保持內存使用率很小。

但最終，你將有測試...

來源

2012-09-08 12:25:44 angainor

我應該選擇高時間複雜度數據結構還是高空間複雜度數據結構以獲得有效的方法？

回答

相關問題