为什么简单字符串连接的复杂度为O(n ^ 2)? [英] Why is the complexity of simple string concatenation O(n^2)?

问题描述

我在几本手册和在线资源中读到，简单字符串连接"的运行时间为O(n ^ 2)?

I read on several manuals and online sources that the running time of "simple string concatenation" is O(n^2)?

算法是这样的:我们获取前2个字符串，创建一个新字符串，将2个原始字符串的字符复制到新字符串中，然后一遍又一遍地重复此过程，直到所有字符串都被串联为止.我们没有使用StringBuilder或类似的实现:只是一个简单的字符串连接.

The algorithm is this: we take the first 2 strings, create a new string, copy the characters of the 2 original strings in the new string, and repeat this process over and over again until all strings are concatenated. We are not using StringBuilder or similar implementations: just a simple string concatenation.

我认为运行时间应类似于O(kn)，其中k =字符串数，n =字符总数.您不会复制相同的字符n次，而是复制k次，因此它不应为O(n ^ 2).例如，如果您有2个字符串，则仅为O(n).基本上是n +(n-x)+(n-y)+(n-z)...但是k次，而不是n次.

I think the running time should be something like O(kn) where k = number of strings, n = total number of characters. You don't copy the same characters n times, but k times, so it should not be O(n^2). For example, if you have 2 strings, it's just O(n). Basically it's n + (n-x) + (n-y) + (n-z)... but k times, not n times.

我在哪里错了?

推荐答案

如果编写一些测试并查看字节码，您会看到 StringBuilder 用于实现串联.有时它会预先分配内部数组以提高执行效率.显然这不是O(n ^ 2)的复杂性.

If you write some tests and look at the byte code you will see that StringBuilder is used to implement concatenation. And sometimes it will pre-allocate the internal array to increase the efficiency to do so. That is clearly not O(n^2) complexity.

这是Java代码.

  public static void main(String[] args) {
      String[] william = {
            "To ", "be ", "or ", "not ", "to ", ", that", "is ", "the ",
            "question."
      };
      String quote = "";
      for (String word : william) {
         quote += word;
      }
   }

这是字节码.

 public static void main(java.lang.String[] args);
      0  bipush 9
      2  anewarray java.lang.String [16]
      5  dup
      6  iconst_0
      7  ldc <String "To "> [18]
      9  aastore
     10  dup
     11  iconst_1
     12  ldc <String "be "> [20]
     14  aastore
     15  dup
     16  iconst_2
     17  ldc <String 0"or "> [22]
     19  aastore
     20  dup
     21  iconst_3
     22  ldc <String "not "> [24]
     24  aastore
     25  dup
     26  iconst_4
     27  ldc <String "to "> [26]
     29  aastore
     30  dup
     31  iconst_5
     32  ldc <String ", that"> [28]
     34  aastore
     35  dup
     36  bipush 6
     38  ldc <String "is "> [30]
     40  aastore
     41  dup
     42  bipush 7
     44  ldc <String "the "> [32]
     46  aastore
     47  dup
     48  bipush 8
     50  ldc <String "question."> [34]
     52  aastore
     53  astore_1 [william]
     54  ldc <String ""> [36]
     56  astore_2 [quote]
     57  aload_1 [william]
     58  dup
     59  astore 6
     61  arraylength
     62  istore 5
     64  iconst_0
     65  istore 4
     67  goto 98
     70  aload 6
     72  iload 4
     74  aaload
     75  astore_3 [word]
     76  new java.lang.StringBuilder [38]
     79  dup
     80  aload_2 [quote]
     81  invokestatic java.lang.String.valueOf(java.lang.Object) : java.lang.String [40]
     84  invokespecial java.lang.StringBuilder(java.lang.String) [44]
     87  aload_3 [word]
     88  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [47]
     91  invokevirtual java.lang.StringBuilder.toString() : java.lang.String [51]
     94  astore_2 [quote]
     95  iinc 4 1
     98  iload 4
    100  iload 5
    102  if_icmplt 70

这篇关于为什么简单字符串连接的复杂度为O(n ^ 2)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！