Java字符串压缩算法的时间复杂度是否为O(n)线性复杂度？

你的这段字符串压缩代码的时间复杂度确实是**O(n)**线性复杂度，理由如下：

• 外层for循环和内层while循环看似是嵌套结构，但实际上每个字符只会被访问一次。内层while循环会直接跳过已经统计过的重复字符，外层循环的i变量会被内层循环推进，不会重复遍历同一个字符。
• StringBuilder的append()操作均为分摊O(1)的时间复杂度，不会对整体线性时间的结论造成影响。

举个例子，针对输入字符串"AAAAABBCDDDEE"，每个字符只会被检查一次，没有冗余的遍历操作，总操作次数和字符串长度n完全成正比。

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);

    }
}

内容的提问来源于stack exchange，提问作者Dharun