这个算法的时间复杂度是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函数首先调用具有O(n)时间复杂度和O(1)空间复杂度的reverseCharacters函数。

然后，for循环最多运行n次，并且它再次调用具有while循环的reverseCharacters函数，该while循环也将运行n次。这是否意味着时间复杂度将合并为O(n²)？

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

- PAujla

---

澄清一下你所说的n是什么意思，答案就会显而易见了。提示：它与reverseCharacters中的message长度无关。 - Joseph Sible-Reinstate Monica

Answer 1

......循环将最多运行n次

正确的。

......并且它再次调用了reverseCharacters, reverseCharacters包含一个while循环，该循环也会运行n次。

这是不正确的。

reverseCharacters在reverseWords遇到空格或字符串结尾时被调用。boundsleftIndex和rightIndex指向单词的起始和结束，并且不会遍历整个字符串。

因此，每个字符在字符串中均见两次，类似于O(n + n)，即O(n)。

例如：

对于字符串abcd efg hijk，显然reverseWords扫描此字符串。

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

- Thiyagu