Java的子串()的时间复杂度
Java的子串()的时间复杂度
提问于 2011-01-13 19:57:55
String#substring()方法在Java中的时间复杂度是多少？
回答 4
Stack Overflow用户
发布于 2012-09-21 06:27:16
在老版本的Java中是O(1) -正如Jon所说，它只是创建了一个具有相同底层char[]的新字符串，以及不同的偏移量和长度。
然而，从Java7更新6开始，这种情况实际上发生了变化。
消除了char[]共享，并删除了偏移量和长度字段。substring()现在只是将所有字符复制到一个新的字符串中。
因此，在Java 7更新6中，子字符串为O(n
Stack Overflow用户
发布于 2013-12-28 04:25:50
现在是线性复杂度。这是在修复了一个子字符串的内存泄漏问题之后。
因此，从Java的1.7.0_06来看，请记住，String.substring现在具有线性复杂度，而不是常数复杂度。
Stack Overflow用户
发布于 2019-01-11 18:34:18
给乔恩的答案加上证据。我也有同样的疑问，并想检查字符串的长度是否对substring函数有任何影响。编写以下代码以检查参数子串实际依赖于哪个参数。
import org.apache.commons.lang.RandomStringUtils;
public class Dummy {
private static final String pool[] = new String[3];
private static int substringLength;
public static void main(String args[]) {
pool[0] = RandomStringUtils.random(2000);
pool[1] = RandomStringUtils.random(10000);
pool[2] = RandomStringUtils.random(100000);
test(10);
test(100);
test(1000);
}
public static void test(int val) {
substringLength = val;
StatsCopy statsCopy[] = new StatsCopy[3];
for (int j = 0; j < 3; j++) {
statsCopy[j] = new StatsCopy();
}
long latency[] = new long[3];
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 3; j++) {
latency[j] = latency(pool[j]);
statsCopy[j].send(latency[j]);
}
}
for (int i = 0; i < 3; i++) {
System.out.println(
" Avg: "
+ (int) statsCopy[i].getAvg()
+ "\t String length: "
+ pool[i].length()
+ "\tSubstring Length: "
+ substringLength);
}
System.out.println();
}
private static long latency(String a) {
long startTime = System.nanoTime();
a.substring(0, substringLength);
long endtime = System.nanoTime();
return endtime - startTime;
}
private static class StatsCopy {
private long count = 0;
private long min = Integer.MAX_VALUE;
private long max = 0;
private double avg = 0;
public void send(long latency) {
computeStats(latency);
count++;
}
private void computeStats(long latency) {
if (min > latency) min = latency;
if (max < latency) max = latency;
avg = ((float) count / (count + 1)) * avg + (float) latency / (count + 1);
}
public double getAvg() {
return avg;
}
public long getMin() {
return min;
}
public long getMax() {
return max;
}
public long getCount() {
return count;
}
}
}在Java 8中执行时的输出为：
Avg: 128 String length: 2000 Substring Length: 10
Avg: 127 String length: 10000 Substring Length: 10
Avg: 124 String length: 100000 Substring Length: 10
Avg: 172 String length: 2000 Substring Length: 100
Avg: 175 String length: 10000 Substring Length: 100
Avg: 177 String length: 100000 Substring Length: 100
Avg: 1199 String length: 2000 Substring Length: 1000
Avg: 1186 String length: 10000 Substring Length: 1000
Avg: 1339 String length: 100000 Substring Length: 1000证明子串函数依赖于请求的子串的长度，而不是字符串的长度。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4679746
复制相关文章
相似问题