java - 该代码的时间复杂度为O(N ^ 2)吗

对于leetcode中的问题之一，这是我的解决方案。通过推论，我得出结论，它具有总体O(N ^ 2)时间复杂度。但是，我想对此进行确认，以免在判断算法的时间/空间复杂度时继续犯同样的错误。

哦，问题如下:

给定输入字符串，逐个单词地反转字符串。
例如“我是你” ==“你是我”

代码如下:

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开始]

值得一提的是，如果其他人有比这更好的解决方案，请随时分享! :)

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

感谢帮助!

编辑:我的意思是询问包含循环的代码部分的时间复杂度。如果问题引起误解/困扰，我谨此致歉。整个代码块都是为了澄清目的。 :)

最佳答案

时间复杂度为O(n)。

每次在append(x)中插入(StringBuilder)都在O(|x|)中完成，其中| x |是您要附加的输入字符串的大小。 (平均独立于构建器的状态)。

您的算法会迭代整个字符串，并对其中的每个单词使用String#substring()。由于单词不重叠，这意味着您一次为每个单词执行一个substring()，并将其附加到构建器中(也是一次)-为每个单词2|x|提供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()方法在输出字符串的大小上是线性的，而不是原始的(您仅复制相关部分，而不是复制所有字符串)。