java - 这个算法的时间复杂度是O(n)还是O(n^2)？

Question

  public static void reverseWords(char[] message) {
    reverseCharacters(message, 0, message.length - 1);
    int currentWordStartIndex = 0;
    for (int i = 0; i <= message.length; i++) {
        if (i == message.length || message[i] == ' ') {
            reverseCharacters(message, currentWordStartIndex, i - 1);
            currentWordStartIndex = i + 1;
        }
    }
}

private static void reverseCharacters(char[] message, int leftIndex, int rightIndex) {
    while (leftIndex < rightIndex) {
        char temp = message[leftIndex];
        message[leftIndex] = message[rightIndex];
        message[rightIndex] = temp;
        leftIndex++;
        rightIndex--;
    }
}

乍一看，时间复杂度为 O(n)，空间复杂度为 O(1)。这也是作者建议的。然而，函数reverseWords首先调用reverseCharacters，其时间复杂度为O(n)，空间复杂度为O(1)。

然后 for 循环将运行最多 n 次，并再次调用verseCharacters，其中包含一个也将运行 n 次的 while 循环。这不是意味着时间复杂度将是 O(n^2) 吗？

如果辅助函数中的代码实际上已实现到reverseWord 函数中，它会改变空间或时间复杂度吗？

Answer 1

[..] the for loop which will run max of n times

正确

[..]and it calls reverseCharacters again which contains a while loop which would also run n times.

这不是真的。

当 reverseWords 遇到空格或字符串末尾时，将调用

reverseCharacters。边界 leftIndex 和 rightIndex 指向单词的开头和结尾，并且不会迭代整个字符串。

因此，字符串中的每个字符都会出现两次，就像 O(n + n) ，即 O(n)。

示例:

对于字符串 abcd efg hijk，很明显 reverseWords 会扫描该字符串。

当它看到空格或字符串末尾时，它会调用reverseCharacters。对于上述字符串，这种情况发生了三次 - 来自 (a - d)、(e - g) 和 (h - k)。它反转边界之间的字符。这些操作中的每一个都不是O(n)。