Друзья, сегодня поговорим о временно́й сложности операций со строками (тип
str
) в Python.
📎 Тип данных
str
представляет собой
неизменяемую последовательность символов. Большинство операций со строками требует просмотра каждого символа строки, поэтому временнáя сложность практически всех строковых операций равна
O(n)
, где
n
— длина строки. Исключением является операция обращения к символу строки по индексу, временнáя сложность которой равна
O(1)
.
📎 Особого внимания заслуживают операции конкатенации и поиска подстроки в строке. Рассмотрим их подробно.
🟪 Конкатенация двух строк, выполняемая в виде операции
s1 + s2
или
s1 += s2
, имеет временну́ю сложность
O(n+m)
, где
n
— длина строки
s1
, а
m
— длина строки
s2
. Как видно, эта операция является ресурсоемкой, поэтому использовать ее нужно аккуратно.
Например, приведенный ниже алгоритм:
def algorithm(n):
result = ''
for _ in range(n):
result += 'A'
return result
выполняет конкатенацию двух строк в цикле, что приводит к постоянному созданию промежуточных строковых значений и увеличению временно́й сложности алгоритма до
O(n²)
.
✔ Более эффективную конкатенацию можно выполнить с помощью строкового метода
join()
. Преимущество такого способа в том, что метод
join()
во время объединения строк не создает промежуточных значений.
Например, в приведенном ниже алгоритме:
def algorithm(n):
result = []
for _ in range(n):
result.append('A')
return ''.join(result)
метод
join()
единожды создает строку нужной длины, поэтому временнáя сложность операции равна всего
O(n)
.
🟪 Поиск подстроки в строке осуществляется с помощью оператора
in
и методов
find()
,
rfind()
,
index()
,
rindex()
,
count()
,
replace()
. Каждый из этих инструментов с версии Python 3.10 для поиска подстроки в строке использует алгоритм, который является комбинацией из трех алгоритмов:
➖алгоритма Бойера – Мура
➖алгоритма Бойера – Мура – Хорспула
➖алгоритма Сандея
В худшем случае этот алгоритм имеет временну́ю сложность
O(n+m)
, а в среднем —
O(n)
, где
n
— длина строки, а
m
— длина подстроки. На практике худший случай достигается редко, поэтому временну́ю сложность операции поиска подстроки в строке с помощью перечисленных выше инструментов принято считать равной
O(n)
.
⏰⏰⏰⏰⏰⏰⏰ Выход нашего нового курса по алгоритмам запланирован на 1 апреля. Вы можете купить его до официального старта со скидкой 20% и получить приятные бонусы. Подробности по ссылке!
Ставьте реакцию:🔥 — если знали временну́ю сложность операций со строками
👀 — если узнали о ней впервые
🔝🔝🔝Сохраняйте пост в избранное, точно пригодится!
✍🏻#поколениеpython #курспоалгоритмам