<分区>
这是一段简单的代码。它的时间复杂度是多少？
for(int i=0;i<n;i++){
String temp="";
for(int j=i;j<n;j++){
temp+=S.charAt(j);
}
System.out.println(temp);
}
N<=5000
上面的代码给出了 TLE 而下一个简单的代码给出了 Wrong Answer:
for(int i=0;i<n;i++){
String temp ="";
for(int j=i;j<n;j++){
}
System.out.println(temp);
}
最佳答案
复杂度实际上是 O(n^3)，如果忽略 JIT 优化(并且很可能在线判断将其关闭)。由于 5000^3 ~= 1.2*10^11，预计会获得 TLE。
时间复杂度说明:
看你的代码，特别注意我加的注释:
for(int i=0;i<n;i++){
String temp="";
for(int j=i;j<n;j++){
temp+=S.charAt(j);
// ^^ THIS IS NOT O(1)^^
}
System.out.println(temp);
}
内部循环的每次迭代都需要 O(|temp|) 时间，其中 |temp| 是 temp 的长度。
回想一下java中的String是不可变的，字符串拼接实际上是在复制旧的底层char[]的同时创建一个新的对象，导致线性时间操作。
那么，让我们检查一下temp 的长度。
temp 的长度在内循环的每次迭代中增加 1，并在外循环的每次迭代中重置。
因此，对于某些i，外循环的每次迭代执行所花费的时间是内循环的所有迭代的总和，即:
Outer(n,i) = 1 + 2 + ... + n-i+1 = (n-i)(n-i+1)/2
现在，对 i 的所有值求和得到我们:
T(n) = sum {Outer(n,i) for i = 0,...,n}
T(n) = (n-0)(n-0+1)/2 + (n-1)(n-1+1)/2 + ... + (n-n)(n-n+1)/2
T(n) = n(n+1)(n+2)/6
last equation是平方和的变体。
我们可以看到T(n)确实在O(n^3)中。
可以通过使用 StringBuider 将复杂度从 O(n^3) 显着提高到 O(n^2)
关于java - 一段简单代码的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30723248/