SetLength的複雜性是什麼？

我經常需要多次調用SetLength來增加一些動態數組的長度。以下代碼的複雜性是什麼？SetLength的複雜性是什麼？

const 
    n = 1000000; 
var 
    a: array of integer; 

for i := 1 to n do 
    SetLength(a, i);

來源

2015-05-05 kien_coi_1997

假設SetLength複雜度爲O（1），那麼由於您調用SetLength n次，您的算法將具有O（n）複雜度。

也許這篇文章可以幫助你進一步相關的問題：https://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

來源

2015-05-05 09:17:41 Alvein

我不確定SetLength的複雜性是O（1）。你假設我在問什麼：「SetLength的複雜性是什麼」。 –

是的，我假設這一點。根據經驗，我認爲SetLength複雜度在最佳情況下爲O（1），在最壞情況下爲O（n）您可能希望嘗試對其進行基準測試以驗證假設 – Alvein

單SetLength調用可以有O（n）的複雜性，因爲如果數組結束後的內存用於別的東西，整個數組必須被複制到一個新的位置（也就是說，它可能必須創建一個全新的數組，從舊數組複製內容，釋放舊數組）。

這將表明您提供的代碼將具有O（n^2）複雜性。但是，如果您對其進行基準測試，則很可能會發現倍數n只會使運行時間加倍，表明整個算法運行在O（n）中，這反過來表明SetLength爲O（1）。最可能發生的情況是內存管理器實際佔用的內存比您要求的內存數量多。因此，在隨後的SetLength調用中，它可以輕鬆地增加數組的長度，因爲數組結尾後的內存實際上已經爲數組保留了。

但是我仍然不會在每次迭代中增加一個動態數組。如果您只提前進行一次SetLength調用，您仍然可以獲得更好的性能（特別是如果您運行數百萬次迭代）。在你的情況，我會做

SetLength(a, n); 
for i := 1 to n do 
    // no need for SetLength here

如果你不知道數組有多大是你可以做這樣的事情

SetLength(a, 16); 
aLength := 0; 
while Whatever do 
begin 
    if aLength = Length(a) then 
    SetLength(a, aLength * 2); 
    ... 
    a[aLength] := ... 
    Inc(aLength); 
    ... 
end;

在這裏，我對數組的初始長度使用16並在陣列變滿時將長度加倍。這些可以根據手頭的問題進行調整。

另外考慮如果您可以使用一些可用的數據結構，例如TList例如您不必擔心自己增長陣列。我不確定在FreePascal中是否有通用版本的TList，但它可能是最好的選擇。

來源

2015-05-06 07:20:21

SetLength的複雜性是什麼？

回答

相關問題