Временная сложность для сегмента кода

Question

Из онлайн-заметок я прочитал следующий фрагмент кода Java для реверсирования строки, которая, как утверждается, имеет квадратичную сложность по времени. Мне кажется, что цикл for для i просто повторяет всю длину s. Как это вызывает квадратичную сложность по времени?

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

Answer 1

public static String reverse(String s)
{
  String rev = " ";
  for (int i=s.length()-1; i>=0; i--)
  rev.append(s.charAt(i); // <--------- This is O(n)
  Return rev.toString();
}

Я скопировал и вставил твой код.Я не уверен, откуда вы это взяли, но на самом деле в String нет метода append.Возможно rev - это StringBuilder или другое Добавляемое .

Answer 2

Я не думаю, что у String есть метод добавления.Таким образом, этот код не будет компилироваться.

Но, перейдя к проблеме квадратичной сложности, давайте предположим, что вы на самом деле добавляете строку с символом, используя оператор «+» или метод String.concat ().Объекты String неизменны.Таким образом, каждый раз, когда вы добавляете строку, создается новая строка большей длины, в нее копируется содержимое старой строки, а затем добавляется последний символ, а предыдущая строка уничтожается.Таким образом, этот процесс занимает все больше и больше времени по мере роста строки.

Добавляемый цикл занимает время O (n), но для каждого цикла вы берете O (n) время, чтобы скопировать строку символ за символом.Это приводит к квадратичной сложности.

Было бы лучше использовать StringBuilder или StringBuffer.Тем не менее, я думаю, что сложность времени, которую вы упомянули, была бы со старыми компиляторами Java.Но новые усовершенствованные компиляторы на самом деле оптимизируют операцию '+' с помощью StringBuilder.

Answer 3

append должен найти конец строки, который является & Omicron; (n). Итак, у вас есть цикл & Omicron; (n), выполненный & Omicron; (n) раз.

Answer 4

Возможно, потому что вызов append не выполняется в постоянное время. Если бы он был линейным с длиной строки, это объяснило бы это.