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

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)

Answer 2

Aleksey O(numberOfWords * averageWordLength)。这是正确的（如果我们暂时忽略 +=），但更一般的答案是根据输入的长度 n。由于 n = numberOfWords * averageWordLength，我们可以说它是 O(n)，或线性的。

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

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

What's the time complexity of below program?

java

big-o