该算法的时间复杂度是否为 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 次，它再次调用 reverseCharacters，其中包含一个 while 循环，该循环也将运行 n 次。 这是否意味着时间复杂度加在一起将是 O(n^2(？

如果来自帮助程序函数的代码实际上被嵌入到 reverseWord 函数中，它会改变空间或时间复杂度吗？

Answer 1

[..] 最多运行 n 次的 for 循环

真

[..]它再次调用 reverseCharacters，其中包含一个 while 循环，该循环也会运行 n 次。

这不是真的。

当reverseWords遇到空格或字符串末尾时调用reverseCharacters。边界leftIndex和rightIndex指向单词的开头和结尾，并且不会循环访问整个字符串。

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

例：

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

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