Time complexity of these 2 program

问题内容:

I am new to complexity analysis. The task is that given a non-empty string like “Code” return a string like “CCoCodCode”. I have these 2 programs which are doing the same thing.

Program 1:

public String stringSplosion(String str) {
    String result = "";
    for (int i=0; i<str.length(); i++) {
        for(int j=0;j<=i;j++)
            result += str.charAt(j);
    }
    return result;
}

So, above one is pretty simple and this program has O(n^2) complexity.

Program 2:

public String stringSplosion(String str) {
    String result = "";
    // On each iteration, add the substring of the chars 0..i
    for (int i=0; i<str.length(); i++) {
        result = result + str.substring(0, i+1);
    }
    return result;
}

From a different StackOverflow question, it seems str.substring() has a time complexity of O(n). In that case, program 2 also has O(n^2) time complexity.

Is my analysis correct or I am missing something?

问题评论:

2  
Yes, you’re right.
1  
Well even more, you can make it a bit faster (but still O(n^2)) by using a StringBuilder instead of the string concatenation. Btw. all Algorithms solving this problem have at least O(n^2) time complexity since the output has length O(n^2).
    
I think you are right. You can always test execution times with really long strings. For example, if you go from length=1000 to length=2000, does execution time increase with a factor 4 for both methods?

答案:

答案1:

In fact, both have the same complexity – O(n^3). That’s because you’re using += for concatenating the answer! there’s a hidden loop there that you didn’t account for, and a classic example of Schlemiel the Painter’s Algorithm. You should use StringBuilder instead, it’s the right way to build a string as you go.

答案评论:

    
@Stefan Indeed! There’s the explicit loop, and the loop in the substring operation, and finally the loop in the + concatenation operation
1  
While this is a good observation, the compiler will convert his string concatenation to a StringBuilder internally. docs.oracle.com/javase/specs/jls/se8/html/…
    
Yes, but not necessarily an useful one. It depends on where it’s declared – inside or outside the loops

原文地址:

https://stackoverflow.com/questions/47755613/time-complexity-of-these-2-program

添加评论