Java中这个字符串压缩算法的时间复杂度是多少？ [重复]

Question

此

Java code

通过将连续重复的

string

替换为后面跟着其

characters

的字符来压缩

count

。例如，字符串

"AAAAABBCDDDEE"

将被压缩为

"A5B2CD3E2"

.

public class StrToCompressedStr {
    public static void main(String[] args)
    {
        StringBuilder list=new StringBuilder();
        String str="AAAAABBCDDDEE";

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            list.append(c);
            int count = 0;

            while (i<str.length() && c == str.charAt(i))
            {
                count++;
                i++;
            }
            i--;
            if (count >= 2)
            {
                list.append(count);
            }
        }
        System.out.println(list);

    }
}

我尝试压缩字符串。这就是我想到的，我的问题是，这真的是 O(n) 线性吗？

Answer 1

代码逐一查看输入字符串中的每个字符。 对于每个字符，它会计算该字符连续重复的次数。 它将字符添加到新字符串中，如果重复多次，它还会添加重复次数。 然后，它会移动到下一个字符。

由于它只遍历输入字符串一次，并且它在循环内执行的所有其他操作不需要太多额外时间，因此运行代码所需的时间与输入字符串的长度成正比。这就是我们所说的 O(n) 时间复杂度，其中“n”是输入字符串的长度。因此，它是线性的 - 如果输入字符串的长度加倍，则运行代码所需的时间也会加倍。