这段代码的时间复杂度是O(N^2)

Question

这是我对leetcode中一道题的解法。通过我的推论，我得出结论，它的总体时间复杂度为 O(N^2)。但是，我想就此得到确认，这样我就不会在判断算法的 time/space 复杂性时继续犯同样的错误。

哦，问题如下：

Given an input string, reverse the string word by word. e.g. "I am you" == "you am I"

代码如下：-

public String reverseWords(String s) {
        //This solution is in assumption that I am restricted to a one-pass algorithm.
        //This can also be done through a two-pass algorithm -- i.e. split the string and etc.

        if(null == s)
            return "";
        //remove leading and trailing spaces
        s = s.trim();
        int lengthOfString = s.length();
        StringBuilder sb = new StringBuilder();
        //Keeps track of the number of characters that have passed.
        int passedChars = 0;
        int i = lengthOfString-1;
        for(; i >= 0; i--){
            if(s.charAt(i) == ' '){
                //Appends the startOfWord and endOfWord according to passedChars.
                sb.append(s.substring(i+1, (i+1+passedChars))).append(" ");
                //Ignore additional space chars.
                while(s.charAt(i-1) == ' '){
                    i--;
                }
                passedChars = 0;
            }else{
                passedChars++;
            }
        }

        //Handle last reversed word that have been left out.
        sb.append(s.substring(i+1, (i+1+passedChars)));

        //return reversedString;
        return sb.toString();
    }

我认为这是一个 O(N^2) 算法的原因：-

循环 = O(n)
StringBuilder.append = O(1)
子字符串方法 = O(n) [截至 Java 7]

关于这一点，如果其他人有比这更好的解决方案，请随时分享！ :)

我的目标是一次性解决方案，因此选择不在循环之前拆分字符串。

感谢帮助！

编辑： 我想问一下包含循环的代码部分的时间复杂度。如果问题是 misleading/confusing，我提前道歉。整个代码块用于说明目的。 :)

Answer 1

时间复杂度为O(n).

对 StringBuilder 的每次插入 (append(x)) 都在 O(|x|) 中完成，其中 |x|是您要追加的输入字符串的大小。（平均而言，与建造者的状态无关）。

您的算法迭代整个字符串，并对其中的每个单词使用 String#substring()。由于单词不重叠，这意味着您对每个单词执行一次 substring()，并将其附加到构建器（也是一次）- 为每个单词 x 提供 2|x|。

总结起来，给你

T(S) = |S| + sum{2|x| for each word x}

但是由于 sum{|x| for each word x} <= |S|，这给你总共：

T(S) = |S| + 2sum{|x| for each word x} = |S| + 2|S| = 3|S|

自|S|是输入的大小（n），这是O(n)

注意重要的部分在jdk7中，substring()方法输出字符串的大小是线性的，而不是原来的（你只复制相关部分，而不是整个字符串）。

Answer 2

这是一个替代解决方案，我认为它的性能可能会好一些。

public String reverseWords(String s) {
    String[] array = s.split(" ");
    int len = array.length;

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append(" ").append(array[len - i - 1]);
    }

    return sb.toString().trim();
}

Answer 3

Amit已经给大家详细解释了复杂度的计算，我想给大家一个更简单的版本。

一般来说，如果我们有嵌套循环，我们认为复杂度为 O(N^2)。但情况并非总是如此，因为您必须对输入的每个第 n 部分执行一些 activity n 次。例如，如果您的输入大小为 3，则必须对每个元素执行 3 次操作。然后，你可以说你的算法有 O(n^2) 复杂度。

由于您只遍历和处理输入字符串的每个部分一次（即使您使用的是嵌套循环），复杂度应该在 O(n) 的数量级。为了证明，阿米特已经做了很多工作。

虽然，我会使用下面的代码来颠倒单词的顺序

String delim = " ";
String [] words = s.split(delim);
int wordCount = words.length; 

for(int i = 0; i < wordCount / 2; i++) {
    String temp = words[i];
    words[i] = words[wordCount - i - 1];
    words[wordCount - i - 1] = temp;
}

String result = Arrays.toString(words).replace(", ", delim).replaceAll("[\[\]]", "");

这段代码的时间复杂度是O(N^2)

Is the time complexity of this code O(N^2)

java

algorithm

performance

substring

time-complexity