Строку сложности манипуляции


Я читал трескать кодирование интервью и в самом начале я попал на странное заявление, что следующая сложность будет \$o(п^2)\$.

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

Я не могу получить его. Почему это \$o(п^2)\$? Здесь я нашел еще одну статью на эту тему.



4750
4
задан 8 августа 2011 в 08:08 Источник Поделиться
Комментарии
3 ответа

Для каждого вызова строку.функция concat(), новый экземпляр string создается. Для создания этого экземпляра, содержание предыдущей строки должен быть скопирован в Новый один плюс содержание сцепленную строку. Это делается для каждой строки в коллекции. Так что если вы посмотрите на это в терминах того, сколько строк объединяются (и не герои срисованы), вы копируете содержимое из n строк, к тому времени вы достигнете п- й итерации и главное, что в худшем случае (на последней итерации). Поэтому он \$O(п^2)\$ производительность.

16
ответ дан 8 августа 2011 в 09:08 Источник Поделиться

Как Джефф указывает на новую строку, создается каждый раз, когда вы делаете += на строку.
И таким образом, правильно объясняет, почему сложность O(2)

Ключевым моментом является Ява.яз.Строка не изменяемы.


Строки являются постоянными; их ценности не могут быть изменены после их создания. Строковые буферы поддерживают изменяемые строки. Потому что объекты string являются неизменными, они могут быть разделены.

Поэтому любая попытка изменить это породило совершенно новую строку (для программистов в большинстве других языков это не странно).

Решение заключается в использовании Java-приложений.яз.StringBuffer. Этот ведет себя как и большинство других языков строкового объекта и позволяет мутации. Цель заключается в том, чтобы построить строку внутри StringBuffer и когда Вы, наконец, закончил тайную это в строку.


Потокобезопасный, изменяемую последовательность символов. Строковый буфер как строку, но может быть изменен. В любой момент времени содержит определенную последовательность символов, но длина и содержание последовательность может быть изменена через определенные вызовы метода.

2
ответ дан 8 августа 2011 в 09:08 Источник Поделиться

Неизменяемость-это не проблема здесь. Можно написать изменяемую строку классе, где это по-прежнему будет \$o(п^2)\$ или неизменяемый класс String Нижнего сложности (Солнце мог бы сделать последним). Проблема здесь заключается в том, что на каждой итерации алгоритма перечитывая строки из предыдущей итерации, для того чтобы создать новую строку.

Чтобы уменьшить его на порядок, нужно переложить ссылок. В некоторых случаях, компилятор очень хорошо может это сделать в любом случае, в зависимости от сложности оптимизации кода. Однако в случае класс String, я думаю, что это еще не дорого, кстати, по дизайну.

StringBuffer может быть изменчива, но я не вижу, как это делает его более эффективным в данном случае. Важно то, что на каждой итерации, он просто добавляет ссылку на список символов, которые вместо того, чтобы чтение каждого пункта по любой причине, будь то скопировать их в новый экземпляр string в строка в этом примере, или по другой глупой причине. Но сосредоточиться на этом, как изменчивость/неизменность вопрос, я думаю, не попадает в точку.

Простая иллюстрация того, что я имею в виду. Ввести строку из письма. На каждой итерации, вы прочитали предыдущую строку создать новую строку, а затем индекс текущей входной строки для добавления новой строки. Общее отношение-это длина строки, полученной на предыдущей итерации, плюс один, который дает вам сложности \$Н^2 - 1\ долл \$o(п^2)\$.

1
ответ дан 8 августа 2011 в 10:08 Источник Поделиться