Теория

Массивы и строки: Основные операции и сложность

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

Инициализация так проста: arr = [], и вам не нужно беспокоиться о типе данных, которые вы храните в списке, или о размере списка.

Технически, массив не может изменять размер. Динамический массив, или список, может. В контексте задач на алгоритмы, когда говорят о массивах, обычно имеют в виду динамические массивы. Мы будем говорить о динамических массивах/списках, но будем использовать слово "массив".

Аналогично, строки реализованы по-разному в различных языках.

Изменяемый: тип данных, который можно изменить.
Неизменяемый: тип данных, который нельзя изменить.
Если вы хотите изменить что-то неизменяемое, вам нужно будет полностью пересоздать это.

Почему нас должно волновать, изменяемо что-то или нет?
Если у вас есть изменяемый массив arr = ["a", "b", "c"] и неизменяемая строка s = "abc", но вы хотите представить "abd", вы легко можете сделать arr[2] = "d", но не можете сделать s[2] = "d".
Таким образом, если вы хотите строку s = "abd", вам нужно будет создать её полностью с нуля. С такой маленькой строкой это не проблема. Но иногда вы имеете дело со строками длиной 100,000 символов, и создание новых версий только для изменения одного символа очень затратно (O(n), где n — размер строки).

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

Давайте отметим сложность при работе с ними и пойдем дальше.