这里的时间复杂度 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