时间戳

首页 > 解决方案 > 这个算法的时间复杂度是 O(n) 还是 O(n^2)？

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

问题描述

  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 函数中，它是否会改变空间或时间复杂度？

标签： javaalgorithmbig-o

解决方案

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

真的

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

这不是真的。

reverseCharactersreverseWords当遇到空格或字符串结尾时调用。boundsleftIndex和rightIndex指向单词的开头和结尾，不会遍历整个字符串。

因此，字符串中的每个字符都被看到两次，就像O(n + n)which is一样O(n)。

例子：

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

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

推荐阅读