批量數組操作比順序操作更快嗎？

Question

說我給出一個數組和函數調用replace：

void replace(from, to, items[]) 

，其任務是在items的元素替換數組元素的範圍[from, to)。
我會假設事先知道數組的最大大小，所以我可以確保數組永遠不會溢出。

我的問題是，如果我給定的置換（例如，形式(from, to, items)的元素）的列表，有可能是我與比執行每個操作順序地更快時間複雜度獲得最終得到的數組？

換句話說，事先知道操作的順序有沒有什麼好處呢，還是比逐一給每個操作（就漸近時間複雜度而言）有什麼好處？

注：看起來這個問題很混亂;我做了而不是打算暗示替換給定範圍的元素的數量與該範圍的大小相同！它可能會更少或更多，從而導致轉變，問題的關鍵在於詢問是否事先了解它們可以避免在最壞情況下轉移等額外工作。

Answer 1

我想這可能不是你正在發現的，但使用Rope可以縮短時間複雜度。它提供像concat這樣的字符串操作，而不用「移動」實際的數組。 （不需要是字符串，任意類型的元素可以用作字母）

根據維基百科（...因爲我還沒有使用過它），繩是一個balaced二叉樹的分段字符串。繩子代表長串連接所有分段的串。 您的replace（）函數可以使用Split（）和Concat（）操作來實現， 這兩個操作只需要O（log（n））時間。在這裏，我把n代表繩子代表的長繩子的長度。

爲了得到正常的數組，可以使用Report（）操作在O（n）時間內轉換繩索。

所以答案是：有一個算法比順序應用字符串操作更快。給數組繩子

所適用的每

• 轉換代替繩子工作。每個操作都以O（log（n））運行，並且不會複製實際的數組項目。
• 將處理後的繩索轉換爲真實數組（這會導致所有物品的複製）。
• 返回它。

Answer 2

它總是線性的，下降到memcpy的水平。加速它的唯一方法是空間交易時間 - 覆蓋數組下標運算符，以便from和to之間的元素指向items中的元素而不是原始數組，這在任何情況下都不是一個好的解決方案。