C＃的空間複雜性排序字符串列表

我正在實現一個程序來排序可能不適合內存的大文件。所有文件將按行排序，所以我想用List來做。C＃的空間複雜性排序字符串列表

我已經計算出內存中有多少行可以分割較小文件中的文件，但是我不知道在內存中需要多少空間來對N個元素列表進行排序。

問題是，知道最大數量的元素（已知大小的字符串）和可用內存，List.Sort方法將需要多少內存空間？

2012-07-13 Sheol

備註：爲將來的問題跳過把謝謝你的筆記和upvote /接受有用的答案。即除了在泡泡分類建議上評論「謝謝」之外，您還可以在其中提供評論。 – 2012-07-13 15:57:49

我不行，我沒有足夠的聲望去做。 – Sheol 2012-07-13 15:59:28

List<T>.Sort使用快速排序算法，即O（log n）空間。

2012-07-13 15:37:06 SLaks

我想象你需要O（n）內存來存儲字符串。 – 2012-07-13 15:38:28

@SamIam：他已經存儲了字符串。 – SLaks 2012-07-13 15:38:59

是的，這取決於你的參考點。你可能會選擇指出它需要一個*額外的* O（log n）空間，否則這是完全正確的。 +1 – BlackVegetable 2012-07-13 15:40:47

快速排序是O(logn)空間的複雜性，因爲它存儲在每個遞歸水平不變的信息（開始和分區的結束），並且最多logn水平有。

合併本身是就地的，就像氣泡排序後備，因此它們是O(1)，因此不計數。

2012-07-13 15:39:39 Blindy

做一些研究：List.Sort()默認使用QuickSort算法，它具有O（logn）空間複雜度。

如果您真的擔心空間複雜性並且不介意較慢的算法，您可以使用具有O（1）空間複雜度的Bubble sort。

2012-07-13 15:39:57 NominSim

我並不擔心空間複雜性，我只需要知道我需要多少空間。但我會考慮這一點。謝謝。 – Sheol 2012-07-13 15:52:41

回答