Java的子串()的时间复杂度

Question

String#substring()Java中方法的时间复杂度是多少？

Answer 1

新答案

从Java 7的一生中更新6,行为substring改变,以创建一个副本-所以每String指char[]它不与任何其他对象共享的,据我所知.所以在那时,substring()成为一个O(n)操作,其中n是子串中的数字.

旧答案:Java 7之前的版本

未记载 - 但在实践中O(1)如果您认为不需要垃圾收集等.

它只是构建一个新String对象,引用相同的底层char[]但具有不同的偏移和计数值.因此,成本是执行验证和构建单个新(合理小)对象所花费的时间.这是O(1),因为谈论基于垃圾收集,CPU缓存等可以随时间变化的操作的复杂性是明智的.特别是,它不直接取决于原始字符串或子串的长度.

Answer 2

在旧版本的Java中它是O(1) - 正如Jon所说,它只是创建了一个具有相同底层char []的新String,以及不同的偏移量和长度.

但是,实际上这已经从Java 7更新6开始改变了.

char []共享被删除,偏移和长度字段被删除.substring()现在只是将所有字符复制到一个新的String中.

因此,子串在Java 7更新6中是O(n)

Answer 3

它现在是线性复杂性.这是在修复子字符串的内存泄漏问题之后.

因此,从Java 1.7.0_06开始,记住String.substring现在具有线性复杂度而不是常量复杂度.

Answer 4

为乔恩的回答添加证据。我有同样的疑问，想检查字符串的长度是否对子字符串函数有任何影响。编写以下代码来检查子字符串实际依赖于哪个参数。

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

证明子串函数取决于请求的子串的长度而不是串的长度。