時間串壓縮算法

的複雜性我試圖從破解代碼採訪本書壓縮串做一個exercice：時間串壓縮算法

實現方法進行使用重複字符計數基本字符串壓縮。例如，字符串aabcccccaaa將變爲 a2blc5a3。如果「壓縮」字符串不會小於原始字符串，那麼您的方法應返回原始字符串。

由作者給出的第一個命題是：

public static String compressBad(String str) { 
    int size = countCompression(str); 
    if (size >= str.length()) { 
     return str; 
    } 
    String mystr = ""; 
    char last = str.charAt(0); 
    int count = 1; 
    for (int i = 1; i < str.length(); i++) { 
     if (str.charAt(i) == last) { 
      count++; 
     } else { 
      mystr += last + "" + count; 
      last = str.charAt(i); 
      count = 1; 
     } 
    } 
    return mystr + last + count; 
}

關於thie算法的時間複雜度，她說：

運行時間爲0（P + K^2），其中p是原始字符串的大小，k是字符序列的數量。例如，如果字符串是aabccdeeaa，那麼有六個字符序列。這是緩慢的，因爲字符串連接在0（N^2）時間

我有兩個主要問題操作：

1）爲什麼時間複雜度爲O（P + K^2），它應該是唯一的O（p）（其中p是字符串的大小）否？因爲我們只做p迭代而不是p + k^2。

2）爲什麼字符串連接的時間複雜度是0（n^2）？我認爲，如果我們有一個string3 = string1 + string2，那麼我們有一個複雜的大小（string1）+大小（string2），因爲我們必須創建兩個字符串的副本，然後將它們添加到一個新的字符串（創建一個字符串是O（1））。所以，我們會有一個增加不是乘法，不是嗎？這對數組來說不是一回事（例如，如果我們使用char數組）？

您能澄清這些問題嗎？我不明白我們如何計算複雜度...

來源

2016-04-30 salamanka44

字符串串聯是O（n），但在這種情況下它被串聯K次。每當你找到一個序列，你必須複製整個字符串+你找到的。例如，如果你有在原始字符串獲得成本總共四個序列，最後一個字符串將是：

(k-3)+ //first sequence 
(k-3)+(k-2) + //copying previous string and adding new sequence 
((k-3)+(+k-2)+k(-1) + //copying previous string and adding new sequence 
((k-3)+(k-2)+(k-1)+k) //copying previous string and adding new sequence

因此複雜度爲O（P + K^2）

來源

2016-04-30 18:01:38 gidim

時間串壓縮算法

回答

相關問題