複製數據結構和空間複雜性

我經常被要求編寫採用某種類型的參數（如字符串）的函數，並以某種方式操縱它，如果它是某種其他數據結構，那將更容易。我是否可以將字符串轉換爲字符數組，並將字符串設置爲空，同時考慮我的函數使用O（1）空間，還是複製所有元素使其成爲O（N），即使我立即刪除另一個副本？我使用Strings作爲例子，因爲它們是不可變的。在另一種情況下，我會嘗試從一個結構中刪除數據，並將其添加到另一個結構中。複製數據結構和空間複雜性

我只是使用String和char []作爲示例。一般來說，我想知道如果複製我的數據，即使我刪除了其他副本，也會減少算法的空間複雜性。

來源

2014-10-11 user137717

由於原件和拷貝同時在內存中（即使這只是簡單的情況），拷貝會減少空間複雜性，所以您需要擁有可用的額外內存。即使您沒有更多可用內存，內存中算法也可以執行。

來源

2014-10-11 00:16:43

我是否認爲我的函數只需要O（1）空間，如果我可以從一個結構中刪除，因爲我建立了另一個結構？就像我可以在從堆棧中刪除時添加到數組列表一樣？ – user137717 2014-10-11 01:19:22

@ user137717這是正確的，假設你有一個恆定大小的數組列表緩衝區（相對於當前大小的某個百分比的緩衝區） – 2014-10-11 01:43:17

@ user137717我需要修改該評論 - 當數組列表被調整大小時通常需要執行另一個副本（例如，你有一個數組列表大小'n'，你分配一個新的數組列表大小'n' + 10，將舊數組複製到新數組，並且釋放舊數組），這意味着該副本將需要線性空間。爲了它需要恆定的空間，你需要將其複製到分塊列表（數組鏈表）中。請注意，像C這樣的語言可能允許使用'realloc'調整原地數組大小（雖然這取決於'realloc'實現） – 2014-10-11 05:13:23

複製數據結構和空間複雜性

回答

相關問題