java - Java 中 String 函数的算法复杂度

Question

我的问题是:

假设您希望 String myString = "SOME_CHARACTERS_THAT_NEED_MODIFICATION"; 看起来像 String ModifiedString = "Some Characters That Need Modification"。 “纯字符串”方法(以及与大小写无关的方法)将(根据需要对此进行优化):

//obtaining the locations of all the occurrences of '_'
int activeIndex = 0;
ArrayList <Integer> indexList = new ArrayList<Integer>();
while (activeIndex != -1)
{
    activeIndex = myString.indexOf('_', activeIndex + 1);
    indexList.add(new Integer(activeIndex));
}
//replacing all '_' with ' '
String tempString = myString.replace('_', ' ');
//declaring empty modifiedString
String modifiedString;
//lowercasing all characters that are not first characters of a word (here, a word is defined as being terminated by '_' or newline
for (int x = 0; x < indexList.size(); x++)
{
    modifiedString += tempString.substring(indexList.get(x), indexList.get(x)+1);
    if (x != indexList.size() - 1)
        //appending first uppercase character of word plus lowercased characters of the rest of the word
        modifiedString += tempString.subString(indexList.get(x)+1,indexList.get(x+1)).toLowerCase();
    else
        //we are near the end of the String (as far as ' ' is concerned)
        modifiedString += tempString.substring(index.get(x), tempString.length().toLowerCase());
}
//moving this modified String to modifiedString
modifiedString = tempString;

我建议执行此操作的另一种方法是将 myString 转储到字符数组中，然后对所有字符进行基于数组的操作。这在 C++ 中很容易；字符串既是字符数组又是对象!然而，我的问题是，这两种算法是否具有相同的复杂性？//作为一个字符数组，我可能可以做一些算术运算，假设字母数字字符在 ASCII 范围内(0 到 127)。事实上，(int)uppercaseChar == (int)lowercaseChar - 32; 对于从 A-Z 范围内的任何 uppercaseChar 以及从 a-z 范围内的任何相应的 lowercaseChar。

char[] 的做法可能类似于(可能需要优化)

//declaring necessary variables and containers
int activeIndex = 0;
ArrayList<Integer> indexList = new ArrayList<Integer>();

while (activeIndex != -1)
{
    //finding all '_'
    activeIndex = myString.indexOf('_', activeIndex + 1);
    //pushing it to indexArray
    indexArray.add(new Integer(activeIndex));
}
//dumping String to char[]
char[] charArray = myString.toCharArray();
for (int x = 0; x < indexArray.size(); x++)
{
    //making every '_' a ' '
    charArray[indexArray.get(x)] = ' ';
    //lowercasing every capitalized character that isn't a first character in a word
}

Answer 1

would both algorithms have the same complexity?

没有。如果输入字符串包含n个连续下划线，则

for (int x = 0; x < indexList.size(); x++)
    modifiedString += tempString.substring(indexList.get(x), indexList.get(x)+1);

将附加一个下划线n次。由于每次循环时都必须以线性时间成本复制 modifiedString 的旧值，因此整个算法需要二次时间。

相比之下，“char[] 方法”需要线性时间。