Java的substring（）的时间复杂度
Java中String#substring()方法的时间复杂度是多less？
新的答案
从Java 7的生命周期中的更新6开始， substring的行为被改为创build一个副本 – 所以每个String指向一个不与任何其他对象共享的char[] ，据我所知。 所以在这一点上， substring()变成了一个O（n）操作，其中n是子串中的数字。
老答案：Java之前的7
无证 – 但在实践中O（1）如果你认为没有垃圾收集是必需的，等等。
它只是build立一个新的String对象引用相同的底层char[]但具有不同的偏移量和计数值。 所以成本是执行validation所需的时间，并构build一个新的（相当小的）对象。 就O（1）而言，基于垃圾回收，CPU高速caching等，讨论可能随时间变化的操作的复杂性是明智的。特别是，它不直接取决于原始string或子string的长度。
在老版本的Java中，它是O（1） – 正如Jon所说的那样，它只是创build了一个具有相同底层char []的新string，以及不同的偏移量和长度。
但是，这实际上是从Java 7 update 6开始的。
char []共享被消除，offset和length字段被删除。 substring（）现在只是将所有的字符复制到一个新的string。
在Java 7更新6中，Ergo子串是O（n）
现在它的线性复杂性，这是修复子串的内存泄漏问题之后。
所以从Java 1.7.0_06记住，String.substring现在有一个线性的复杂性，而不是一个常量。
O（1）因为没有复制原始string，它只是创build一个新的包装对象具有不同的偏移量信息。
从下面判断你自己，但是Java的性能缺点在别的地方，而不是在string的子string中。 码：
public static void main(String[] args) throws IOException { String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" + "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx"; int[] indices = new int[32 * 1024]; int[] lengths = new int[indices.length]; Random r = new Random(); final int minLength = 6; for (int i = 0; i < indices.length; ++i) { indices[i] = r.nextInt(longStr.length() - minLength); lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength); } long start = System.nanoTime(); int avoidOptimization = 0; for (int i = 0; i < indices.length; ++i) //avoidOptimization += lengths[i]; //tested - this was cheap avoidOptimization += longStr.substring(indices[i], indices[i] + lengths[i]).length(); long end = System.nanoTime(); System.out.println("substring " + indices.length + " times"); System.out.println("Sum of lengths of splits = " + avoidOptimization); System.out.println("Elapsed " + (end - start) / 1.0e6 + " ms"); }
输出：
子串32768次 分割长度的总和= 1494414 经过2.446679毫秒
如果是O（1），则取决于。 如果你只是在内存中引用相同的string，然后想象非常长的string，你使子string和停止引用长一个。 长时间释放内存不是很好吗？
