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

@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. Так?

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

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

	Конкатенация строк в цикле 29.07.2022, 18:34. Показов 2308. Ответов 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