Java String在内部表示为一个简单的char[]字符数组。String#substring()方法最终调用构造函数返回一个 new 字符串，因为Java字符串是不可变的。下面是该构造函数的source code：

public String(byte[] ascii, int hibyte, int offset, int count)
{
    if (offset < 0)
      throw new StringIndexOutOfBoundsException("offset: " + offset);
    if (count < 0)
      throw new StringIndexOutOfBoundsException("count: " + count);
    // equivalent to: offset + count < 0 || offset + count > ascii.length
    if (ascii.length - offset < count)
      throw new StringIndexOutOfBoundsException("offset + count: "
                          + (offset + count));
    value = new char[count];
    this.offset = 0;
    this.count = count;
    hibyte <<= 8;
    offset += count;
    while (--count >= 0)
      value[count] = (char) (hibyte | (ascii[--offset] & 0xff));
}

正如您所看到的，获取子字符串的成本包括分配一个新的char[]数组，然后遍历源字符串的数组，一次一个字符，以填充新数组。这是一个线性运算，因此应该以O(N)为界，其中N是源字符串中的字符数。保存新子字符串所需的空间边界也是O(N)。

Java子串的时间复杂度

Java子字符串方法的时间复杂度是O（n），如Tim Biegeleisen所述，其中n是提取的子字符串的长度，但这里是substring(int beginIndex, int endIndex)的最新源代码

public String substring(int beginIndex, int endIndex) {
    int length = length();
    // Bounds checking
    Preconditions.checkBoundsBeginEnd(beginIndex, endIndex, length);
    if (beginIndex == 0 && endIndex == length)
        return this;
    int subLen = endIndex - beginIndex;
    // Creating the substring
    return isLatin1() ? StringLatin1.newString(value, beginIndex, subLen)
                      : StringUTF16.newString(value, beginIndex, subLen);
}

static void checkBoundsBeginEnd(int begin, int end, int length) {
    Preconditions.checkFromToIndex(begin, end, length, Preconditions.SIOOBE_FORMATTER);
}

public static <X extends RuntimeException>
int checkFromToIndex(int fromIndex, int toIndex, int length,
                     BiFunction<String, List<Number>, X> oobef) {
    if (fromIndex < 0 || fromIndex > toIndex || toIndex > length)
        throw outOfBoundsCheckFromToIndex(oobef, fromIndex, toIndex, length);
    return fromIndex;
}

说明：

1. substring实现在创建子字符串之前调用checkBoundsBeginEnd对beginIndex和endIndex参数执行边界检查。这确保索引在有效范围内。
2. checkBoundsBeginEnd方法调用checkFromToIndex来执行实际的边界检查。它检查fromIndex是否小于0，fromIndex是否大于toIndex，或者toIndex是否大于length。如果这些条件中的任何一个是true，则会引发异常。
3. checkBoundsBeginEnd和checkFromToIndex的时间复杂度都是O（1），因为边界检查涉及简单的整数比较，并且抛出异常是一个常数时间操作。
4. substring实现的总时间复杂度为O(subLen)，其中subLen是创建的子字符串的长度。这是由于创建了新的字符串对象，这涉及到从原始字符串复制字符。实际的时间复杂度取决于StringLatin1.newString和StringUTF16.newString的实现。其他操作，如长度检索和相等性检查的时间复杂度为O（1）。

计算程序实际耗时

关于测量程序的实际执行时间，Java提供了几种测量执行时间的方法：

1. System.currentTimeMillis()：你可以捕获你想要测量的代码块之前和之后的当前时间，并计算差值以获得以毫秒为单位的执行时间。

long startTime = System.currentTimeMillis();
// Your code block here
long endTime = System.currentTimeMillis();
long executionTime = endTime - startTime;

1. System.nanoTime（）：该方法提供纳秒级的测量执行时间的精度。它类似于currentTimeMillis（），但分辨率更高。

long startTime = System.nanoTime();
// Your code block here
long endTime = System.nanoTime();
long executionTime = endTime - startTime;

通过使用这两种方法中的任何一种，您都可以测量程序所花费的实际时间并评估其性能。但是，请记住，测量的时间可能会受到各种因素的影响，例如当前系统负载和其他正在运行的进程。要获得更准确的性能分析，您可以考虑使用分析器或专用的性能监视工具。
此外，如果您正在使用Spring框架，则可以利用SpringAOP（面向方面编程）来度量程序的执行时间。AOP允许您将横切关注点（如日志记录、性能监视或安全性）与核心业务逻辑分离。查看本文Spring Performance Logging来自baeldung