这2个程序的时间复杂性

Question

我是复杂性分析新手。任务是给定一个非空字符串（如“Code”）返回一个字符串（如“CCoCodCode”）。我有两个程序在做同样的事情。

程序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;
}

所以，上面的一个非常简单，这个程序有O（n^2）复杂度。

程序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;
}

从另一个StackOverflow问题来看，str.substring（）的时间复杂度似乎为O（n）。在这种情况下，程序2也具有O（n^2）时间复杂度。

我的分析是正确的还是遗漏了什么？

Answer 1

请原谅缩进，但这本质上是一个满足测试的解决方案。

    public String stringSplosion(String str) {
      // Empty String test
      if (str.length() == 0) 
        return str;

      StringBuilder sb = new StringBuilder();

      for (int i=0; i<=str.length() ; i++) {
        sb.append(str.substring(0,i));
      }
      return sb.toString();
   }

Answer 2

事实上，两者都有相同的复杂性-O（n^3）。这是因为您使用的是串联答案！这里有一个隐藏的循环，你没有解释，这是画家施莱米尔算法的一个经典例子。您应该使用StringBuilder，这是一种在运行时构建字符串的正确方法。