public String getString()
String s= "";
for(int i =0 ; i < LARGE_NUMBER ; i++) {
s += "a"
}
Пожалуйста, используйте ссылку "есть вопрос или комментарий", чтобы ответить на ответ. Он уведомит ответчика о вашем комментарии, чтобы он мог вернуться и ответить.
Используйте ссылку улучшить вопрос для редактирования/обновления вашего вопроса.
Я думаю, что он меньше, чем O(N^2), потому что он содержит только 1 для цикла.
Копирование после перераспределения также может занять цикл...
Мой результат-N^2 (+1 - для копирования возвращаемого значения) :)
@Eugen хорошо, так что вы говорите, что s+=a будет эквивалентно другому циклу for
Да, это может быть эквивалентно другому циклу :)
deppends по реализации строки.
Если строка содержит большое число байтов памяти в начале, то сложность равна O(N).
Если строка каждый раз увеличивается на один байт памяти с дальнейшим перемещением, то это O(N^2).
Если перед его использованием размер неизвестен, и вам нужно переместить его, то вы можете сделать его быстрее, удвоив размер памяти, когда емкости недостаточно. Я думаю, что это должно быть что-то вроде O(log2(N+1)) с добавлением O(N) для операции добавления.
Я бы сказал, что больше, чем O(N), но меньше, чем O(N^2).
Вероятно, потому, что в какой-то момент строку нужно будет перераспределить и скопировать.
Если строка является строкой STL (например), то она будет удвоена (я думаю), когда она будет слишком мала, чтобы добавить к ней новую букву.
так что у вас будет :
""размер строке = 0;
"a" : размер строки = 1; // удвоьте размер и скопируйте строку.
"aa" : размер строки = 2; // удвойте размер и скопируйте строку.
"aaa_" и "aaaa" : размер строки = 4; // удвоьте размер и скопируйте строку
"ааааа___", "аааааа__", "аааааааа", "аааааааа" : размер строки = 8;...
...
подумайте об этом.
Если вам нужно оптимизировать это, то зарезервируйте достаточно большую строку, чтобы уменьшить количество раз, когда новая строка будет повторно выделена и скопирована.
(технически) в новом C++ копия строки будет в основном устранена с помощью оператора "переместить"; поэтому вам нужно будет только заранее изменить размер строки.
М
Copy vs Move здесь не участвует: += не копирует, он просто увеличивает счетчик размера, а добавленный символ копируется (он должен быть, так как он должен войти в строковый буфер извне: символ, как и любой встроенный тип, поскольку любой "регистровый тип", который "перемещается", на самом деле "копируется": вы можете "перемещать" только те вещи, доступ к которым осуществляется косвенно).
Если размер превышает емкость, выделяется новый более широкий буфер, копируется содержимое (перемещение и копирование символов точно такие же), а старый буфер отклоняется.
Вы можете "переместить" буфер из строки в другую, но перемещение буферов в этом контексте не имеет смысла, так как для его увеличения вам нужно изменить его (следовательно, вы необходимость другой).
Когда вектор будет изменен, появится копия, и в новой реализации C++ будет использоваться оператор перемещения (я уверен, что видел видео об этом, сделанное Стефаном т. Лававеем из Microsoft )
Да, но это "перемещение" переместит отдельные символы из старого (малого) буфера в новый (большой), и, следовательно, он не будет отличаться от копии, так как вы не можете повторно использовать старый буфер.
Преимущество происходит, если вектор является вектором<unique_ptr<что-то>>: В этом случае ptr-s "перемещаются" из одного буфера в другой, фактически отключая разрушение заостренных объектов из разрушающего буфера деструкторами ptr-S.