Почему сложность простой конкатенации строк O (n ^ 2)? - PullRequest
Новая
       25

Почему сложность простой конкатенации строк O (n ^ 2)?

0 голосов
/ 09 октября 2019

Я прочитал в нескольких руководствах и онлайн-источниках, что время "простой конкатенации строк" равно O (n ^ 2)?

Алгоритм такой: мы берем первые 2 строки, создаем новуюstring, скопируйте символы 2 исходных строк в новую строку и повторяйте этот процесс снова и снова, пока все строки не будут объединены. Мы не используем StringBuilder или подобные реализации: просто простая конкатенация строк.

Я думаю, что время выполнения должно быть чем-то вроде O (kn), где k = количество строк, n = общее количество символов. Вы не копируете одни и те же символы n раз, но k раз, поэтому это не должно быть O (n ^ 2). Например, если у вас есть 2 строки, это просто O (n). В основном это n + (nx) + (ny) + (nz) ... но k раз, а не n раз.

Где я ошибаюсь?

Ответы [ 2 ]

2 голосов
/ 09 октября 2019

Здесь необходимо точное постановка задачи:

Необходимо рассмотреть две метрики: сколько места требуется и сколько времени требуется. В этой заметке рассматриваются требования к времени.

Операция конкатенации указывается для объединения только двух строк за раз, при этом конкатенация выполняется с левой ассоциацией:

((k1 + k2)+ k3) ...

Есть два параметра, которые можно рассмотреть, и два способа просмотра второго параметра.

Первый параметр - это общий размер (в символах)строки, которые должны быть объединены.

Второй параметр: либо количество строк, которые должны быть объединены, либо размер каждой из строк, которые должны быть объединены.

С учетом первого случая:

n - Общий размер (в символах) строк, подлежащих объединению.

k - Общее количество строк, подлежащих объединению.

Время конкатенации примерно равно:

(н / к) * (k ^ 2) / 2

Или с точностью до постоянной фабрики:

n* k

Затем, для фиксированного 'k', конкавремя растяжения линейно!

Принимая во внимание второй случай:

n - Общий размер строк

m - Размер каждой подстроки

Это соответствует предыдущему случаю, но с:

k = n / m

Предварительная оценка тогда становится:

n * k = n * (n / m) = n ^ 2 / m

То есть для фиксированного 'm' время конкатенации квадратично.

2 голосов
/ 09 октября 2019

Если вы напишете несколько тестов и посмотрите на байт-код, вы увидите, что StringBuilder используется для реализации конкатенации. И иногда он будет предварительно выделять внутренний массив для повышения эффективности. Это явно не O (n ^ 2) сложность.

Вот код 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
...