这里的时间复杂度 O(N^2) 怎么样？

Question

我已经知道这个问题的答案是 O(N^2)，但我不知道如何回答。我知道for循环运行sN次，但是怎么会运行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是不可变的-[=10的新副本=] 在每次串联时创建。