java - 反向字符串和附加后缀的性能测量

Question

我正在阅读有关字符串反转的内容:

第一个代码:

public static String reverse(String s) {
  String rev = "";
  for (int i = s.length() - 1; i >= 0; i--)
     rev += s.charAt(i);
  return rev;
}

第二个代码:

public static String reverse(String s) {
   StringBuilder rev = new StringBuilder();
   for (int i = s.length() - 1; i >= 0; i--)
      rev.append(s.charAt(i));
   return rev.toString();
}

有人提到使用字符串我们有二次时间，使用字符串生成器我们有线性时间。

在第 9 页上，关于后缀的排列在这里使用字符串更好。

我不明白作者在上述两种情况下是如何得出结论的。

有人可以帮我吗？

Answer 1

在第一个代码中:

public static String reverse(String s) {
   String rev = "";
   for(int i = s.length() - 1; i >= 0; i--)
      rev += s.charAt(i);
   return rev;
}

每次执行rev += s.charAt(i);，都会创建一个StringBuilder，那么rev的内容就是追加，然后追加s.charAt(i)，然后将StringBuilder转换为String。那将是 s.length() - 1 StringBuilder 和相同数量的字符串。

在第二个版本中:

public static String reverse(String s) {
   StringBuilder rev = new StringBuilder();
   for(int i = s.length() - 1; i >= 0; i--)
      rev.append(s.charAt(i));
   return rev.toString();
}

只有一个 StringBuilder 和一个 String。

关于您的第二个困惑，能否详细说明一下？很难说出作者的意思。