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

Question

这是我的解决方案中的一个问题的解决方案.通过我的推论,我得出结论,它具有总体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)算法: -

1. 循环= O(n)
2. StringBuilder.append = O(1)
3. 子串方法= O(n)[从Java 7开始]

在这方面,如果其他人有比这更好的解决方案,请随时分享!:)

我的目标是一次通过解决方案,因此选择在循环之前拆分字符串.

感谢帮助!

编辑:我想问一下包含循环的代码部分的时间复杂性.如果这个问题误导/混淆,我会提前道歉.整个代码块用于澄清目的.:)

Answer 1

时间复杂性是O(n).

每个插入(append(x))到a 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 | 是input(n)的大小,这是O(n)

注意,重要的部分是在jdk7中,该substring()方法在输出字符串的大小上是线性的,而不是原始的(您只复制相关部分,而不是所有字符串).