这里的时间复杂度 O(N^2) 如何

Question

我已经知道这个问题的答案是O(N^2)，但我看不出如何。我知道 for 循环运行了 N 次，但它怎么能运行N^2次呢？

public static String rev(String s) {
    String r = "";
    int N = s.length();
    for (int i = 0; i < N; i++) {
        r = s.charAt(i) + r;
    }
    return r;
}

Answer 1

在Java中，循环中的String连接r = s.charAt(i) + r是O(N^2)的，因为Strings是不可变的 - 在每个连接上都会创建一个String的新副本。