Конкатенация строк в цикле

@lunfus · Регистрация: 29.07.2022

Студворк — интернет-сервис помощи студентам

Добрый день. Вычитал в интернете, что конкатенация строк в цикле даёт сложность O (n ^ 2)
Можете, пожалуйста, объяснить, как объясняется такая сложность?
Читал, что при конкатенации создаются новые строки. Но как из этого следует, что операций будет n * n?

@alilxxey · 29.07.2022, 19:47

Рассмотрим этот вопрос в целом для разных языков.

Случай первый. Строки изменяемые, строка представляет собой указатель на некий массив (или иную структуру данных) символов (+ возможно обёртка с функциями). Примеры языков - С (char *) и С++ (string).

В этом случае код из вопроса по сути вырождается в обычное добавление элемента в массив. И если это не низкокачественная лаба самописная реализация то сложность добавления (аммортизированная) будет не больше чем длина того что добавляется.

Тогда очевидно сложность на 1 итерацию будет O(1) а суммарно O(len).

Плюсы данного подхода - скорость работы (добавление, возможность замены символов, быстрое создание подстрок). Минусы - нужно быть очень внимательным что и как меняется в строке, особенно в многопоточных реализациях.

И 2 случай - строки неизменяемые. Т.е. объект строка создаётся 1 раз и не может прямым или косвенным образом изменять своё состояние. Это характерно например для Java.

В этом случае происходит каждый раз создание временного объекта, в который копируется вся старая строка + то что нужно добавить. Т.е. грубо говоря (псевдокод)

@s - string
r[0] = ''
for i =1: i <= s.length(); i++
r[i] = String.gen(r[i-1] , s[i-1]);
И мы создаём Len строк, длинной от 0 до Len включительно, несложно заметить что их суммарная длина будет Len*(Len+1)/2 ~ O(Len^2).

Кстати при отсутствии нормального сборщика мусора (но обычно он есть в таких языках) можно весьма просесть по памяти.

Плюсы и минусы можно сказать обратные, работать проще но медленнее.

Но в каждом таком языке есть механизм которые позволяют создавать подобное не теряя в производительности. Это может быть конструктор строки из коллекции или специальные утилитарные классы (StringBuiled и подобное). Использование их позволяет существенно ускорить процесс и достичь в данном примере асимптотики O(len).

Умный компилятор, если может доказать эквивалентность кода (а в такой простой ситуации это несложно) может заменить прямую конкатенацию строк на утилитарную, обеспечив выигрыш в скорости. Именно это и произошло в Питоне в примере http://ideone.com/wqfd8C.

источник

Добавлено через 8 секунд

Добавлено через 17 секунд

Добавлено через 22 секунды
источник stackowerlfow, не дает вставить ссылку

@Red white socks · 29.07.2022, 20:34

Просто иллюстрация к сказанному выше

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from time import time
import matplotlib.pyplot as plt
import numpy as np
 
def calc_time(n, f, repeat = 100):
    start = time()
    for _ in range (repeat):
        _ = f(n)
    return time()-start
 
def foo(n):
    a, char = '', 'a'
    for _ in range(n):
            a = a + char
 
 
x = np.array([100, 1000, 2000, 5000, 10000, 15000, 20000])
y=np.empty(len(x))
 
for i in range(len(x)):
    y[i]= calc_time(x[i], foo)
           
a, b = np.polyfit(x, y, 1)
      
plt.scatter(x, y, c="red")
plt.plot(x, a*x+b)
plt.show()

@Red white socks · 29.07.2022, 20:35

Как видим, зависимость в питоне линейная

@lunfus · 29.07.2022, 23:24 **[ТС]**

А правильно ли я понимаю, что, когда в случае с Java, копируется вся старая строка, это происходит как-то посимвольно? Из-за этого копирование старой строки длины len сопровождается len операциями, которые и складываются в сумму 1 + 2 + ... + len. Так?

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@lunfus 0 / 0 / 0 Регистрация: 29.07.2022 Сообщений: 2

	Конкатенация строк в цикле 29.07.2022, 18:34. Показов 2295. Ответов 4 Метки нет (Все метки) Добрый день. Вычитал в интернете, что конкатенация строк в цикле даёт сложность O (n ^ 2) Можете, пожалуйста, объяснить, как объясняется такая сложность? Читал, что при конкатенации создаются новые строки. Но как из этого следует, что операций будет n * n? 0

@alilxxey 712 / 351 / 120 Регистрация: 09.12.2020 Сообщений: 918
	29.07.2022, 19:47
	Рассмотрим этот вопрос в целом для разных языков. Случай первый. Строки изменяемые, строка представляет собой указатель на некий массив (или иную структуру данных) символов (+ возможно обёртка с функциями). Примеры языков - С (char ) и С++ (string). В этом случае код из вопроса по сути вырождается в обычное добавление элемента в массив. И если это не низкокачественная лаба самописная реализация то сложность добавления (аммортизированная) будет не больше чем длина того что добавляется. Тогда очевидно сложность на 1 итерацию будет O(1) а суммарно O(len). Плюсы данного подхода - скорость работы (добавление, возможность замены символов, быстрое создание подстрок). Минусы - нужно быть очень внимательным что и как меняется в строке, особенно в многопоточных реализациях. И 2 случай - строки неизменяемые. Т.е. объект строка создаётся 1 раз и не может прямым или косвенным образом изменять своё состояние. Это характерно например для Java. В этом случае происходит каждый раз создание временного объекта, в который копируется вся старая строка + то что нужно добавить. Т.е. грубо говоря (псевдокод) @s - string r[0] = '' for i =1: i <= s.length(); i++ r[i] = String.gen(r[i-1] , s[i-1]); И мы создаём Len строк, длинной от 0 до Len включительно, несложно заметить что их суммарная длина будет Len(Len+1)/2 ~ O(Len^2). Кстати при отсутствии нормального сборщика мусора (но обычно он есть в таких языках) можно весьма просесть по памяти. Плюсы и минусы можно сказать обратные, работать проще но медленнее. Но в каждом таком языке есть механизм которые позволяют создавать подобное не теряя в производительности. Это может быть конструктор строки из коллекции или специальные утилитарные классы (StringBuiled и подобное). Использование их позволяет существенно ускорить процесс и достичь в данном примере асимптотики O(len). Умный компилятор, если может доказать эквивалентность кода (а в такой простой ситуации это несложно) может заменить прямую конкатенацию строк на утилитарную, обеспечив выигрыш в скорости. Именно это и произошло в Питоне в примере http://ideone.com/wqfd8C. источник Добавлено через 8 секунд Добавлено через 17 секунд Добавлено через 22 секунды источник stackowerlfow, не дает вставить ссылку 1

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	29.07.2022, 20:35
	Как видим, зависимость в питоне линейная 0

@lunfus 0 / 0 / 0 Регистрация: 29.07.2022 Сообщений: 2
	29.07.2022, 23:24 [ТС]
	А правильно ли я понимаю, что, когда в случае с Java, копируется вся старая строка, это происходит как-то посимвольно? Из-за этого копирование старой строки длины len сопровождается len операциями, которые и складываются в сумму 1 + 2 + ... + len. Так? 0