这个“字符串压缩”算法的时间复杂度是多少? [重复]

问题描述 投票:0回答:1

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) 线性吗?

java string time-complexity
1个回答
1
投票

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

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

© www.soinside.com 2019 - 2024. All rights reserved.