Почему этот алгоритм объединения строк делает так много шагов? - PullRequest
Новая
       5

Почему этот алгоритм объединения строк делает так много шагов?

1 голос
/ 09 ноября 2019

Основываясь на книге Взлом собеседования по кодированию (стр. 90), следующий алгоритм требует времени O (xn²) (где «x» представляет длину строки, а «n» - количествостроки). Код в Java. Кто-нибудь может объяснить, как мы получаем такое время выполнения? 

String joinWords(String[] words)
{
    String sentence = "";
    for(String w : words)
    {
         sentence = sentence + w;
    }

    return sentence;
}

1 Ответ

3 голосов
/ 11 ноября 2019

Для каждой строки, которая соединяется с sentence, создается новый StringBuilder, к нему добавляются две строки с помощью метода StringBuilder.append, а затем полученная строка создается с помощью метода StringBuilder.toString. Сложность этой операции составляет O (n_1 + n_2), где n_1 и n_2 - длины строк.

В этом коде цикл выполняется n раз, и каждый раз, когда он выполняется, строка sentenceдлины O (xn) соединяется со строкой w длины x. Следовательно, общая сложность равна n * O (xn + x) = O (xn ^ 2), как и ожидалось.

Для скептиков, вот разобранный байт-код метода joinWords;Я скомпилировал его, используя javac 10.0.1 (это версия, которую я сейчас должен передать). StringBuilder используется от позиций 25 до 41, которые находятся внутри цикла (см. 48: goto 12). 

  java.lang.String joinWords(java.lang.String[]);
    Code:
       0: ldc           #2                  // String
       2: astore_2
       3: aload_1
       4: astore_3
       5: aload_3
       6: arraylength
       7: istore        4
       9: iconst_0
      10: istore        5
      12: iload         5
      14: iload         4
      16: if_icmpge     51
      19: aload_3
      20: iload         5
      22: aaload
      23: astore        6
      25: new           #3                  // class java/lang/StringBuilder
      28: dup
      29: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      32: aload_2
      33: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      36: aload         6
      38: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      41: invokevirtual #6                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      44: astore_2
      45: iinc          5, 1
      48: goto          12
      51: aload_2
      52: areturn
...