以下程序的时间复杂度是多少？

Question

这个程序的时间复杂度是多少？我们根据任意大的输入计算时间复杂度。在此示例中，输入字符串可能非常大，但如果它没有空格，那么它只是 O(n(。如果字符串有空格，它将是 O(n * numberOfWords(，我可以将其视为 O(n^2( 时间复杂度吗？提前谢谢你！

public static String revEachWord(String str) {
String reversed = "";
String[] words = str.split(" ");

for(String word : words) {
String reversedWord = "";
for(int i = word.length() - 1; i >= 0; i--) {
reversedWord += word.charAt(i);
}
reversed += reversedWord + " ";
}

return reversed.trim();
}

Answer 1

阿列克谢指出这是O(numberOfWords * averageWordLength)。这是正确的(如果我们暂时忽略+=(，但更一般的答案是输入的长度，n.既然n = numberOfWords * averageWordLength，我们可以说它是O(n)的，或者说是线性的。

但这并不完全正确。正如chrylis在评论中指出的那样，由于您使用+=来构建字符串，因此需要更长的时间：每个副本O(n)，numberOfWords总副本，O(n * numberOfWords)总数，或在最坏的情况下O(n^2)。(实际上，它可能比这更糟糕;我没有考虑嵌套循环中的+=。伊克斯。最好开始使用StringBuilder来获得良好的O(n)运行时间。

Answer 2

O(字数 * 平均字长(