如何優化N個字符串

如果我們給定的n字符串，其長度和一個附加（字符串S1，S2線）函數，這將字符串連接在一起S2與S1和S3返回的級聯的成本。我們如何優化將所有這些字符串連接成一個大字符串的成本。如何優化N個字符串

如果沒有給出這樣的功能，我們可以簡單地創建一個大小爲（N1 + N2 + ... NN）的輸出字符串，並保持追加到它的每個字符串的字符。但是，使用此函數時，我們必須遍歷輸入字符串s1以查找它的結尾，然後開始將字符串s2連接到它。

所以如果字符串的長度是2，6，1，3，4 ..

add (s1, s2) traversal for length 2, op string of length 8 
add (s1, s3) traversal for length (2+6) op string of length 9 
add (s1, s4) traversal for length (2+6+1) op string of length 12 
add (s1, s5) traversal for length (2+6+1+3) op string of length 16...and so on..

來源

2012-10-11 user1071840

你可以提供一個更精確定義你認爲add（）操作的「成本」是什麼？ – rici

我舉了一個例子，這裏的成本是指我必須遍歷整個字符串的次數，並且遍歷大小根據輸入字符串的大小而增長。 – user1071840

"with this function given we'd have to traverse input string s1 
to find it's end and then start concatenating string s2 to it. "

您可以通過Concat的字符字符串的字符權當你穿越它。將一個小字符串附加到結果字符串後，可以獲得指向結果字符串結尾的指針。因此，在添加下一個小字符串時，請使用該字符串，以便您不必一直遍歷到該位置。

來源

2012-10-11 04:59:00

Thera是這樣做的兩種方式。

對數組進行排序，然後保持連接，這樣會降低成本。

時間複雜度O（nlogn）其中n是陣列的尺寸。（假如你有使用快速排序）空間複雜度爲O（LOGN）
創建array.Now的最小堆從堆中取出1日2分鐘，加入他們
並添加再次堆，需要多少時間？

創建最小堆需要O（N）。刪除第一個和第二個Min將採取O（n）+ O（n），等待如何？，用最後一個元素替換root並調用heapify，則需要O（logn），因此不會刪除。現在，我們要做同樣的事情
其餘的n-2個元素，因此將採取總O（N-2（LOGN））那是最糟糕的，添加兩個元素需要O（1）和插回，並再次調整堆會取O（logn）總的來說它是O（nlogn）的順序，我們也可以在這種情況下看到更多的呼叫和指令需要。

整個問題只是需要排序的數組，我們可以將成本最小化級聯，但如果我們需要更多地考慮選擇合適的排序算法，如果我們考慮的時間安空間

來源

2013-09-05 07:26:59 pyshcoguy

其實OP提出的問題並不清楚，因此目前還不清楚這個答案試圖達到什麼目的。 – justhalf

@justhalf，問題提出以最小化連接兩個字符串的成本，讓我們的例子1,5,2是給定的字符串的長度在陣列（未排序，追加按順序） 1 + 5 = 6 6 + 2 = 8 總成本= 14您可以優化總成本嗎？是的，如果對這個數組進行排序，它會是1 2 5，然後追加1 + 2 = 3，然後3 + 5 = 8，因此總成本將爲11，因此排序是實現優化的一種方式。 – pyshcoguy

如何優化N個字符串

回答

相關問題