Структура данных Массив. Сложность операций поиска, вставки, удаления.

Вы уже знаете, как оценивать сложность алгоритмов. Теперь рассмотрим сложность операций вставки, поиска и удаления для стандартных структур данных.

Начнём с массивов. В разных частях массива сложность одной и той же операции может различаться.

Вставка элемента

Гоша записывает, какие фильмы он хотел бы посмотреть:

Скопировать кодPYTHON
films_wish_list = ["Джон Уик 3", "Аватар 2", "Форсаж 9", "Индиана Джонс 5", "Бэтмен"]

Как вы думаете, сколько элементарных операций нужно, чтобы добавить ещё один фильм?

Кажется, всего одна — взять и дописать элемент. Но в какое место памяти компьютера записать? Чтобы решить это, нужно знать номер ячейки в памяти. Зная, сколько в списке элементов и где хранится первый из них, легко определить, куда записать новый элемент. Только сначала надо определить длину массива.

Сложность операции добавления зависит от того, знаем мы длину массива или нет. Допустим, вы пишете на Python. В этом языке длина объектов, для которых её можно определить, хранится в специальной структуре, привязанной к объекту. В нашем примере этот объект –– список фильмов. Когда вы добавляете или удаляете элемент, значение длины меняется.

То есть можно сразу узнать номер последней заполненной ячейки массива. Значит, сложность операции вставки элемента в конец списка O(1).

Скопировать кодPYTHON
films_wish_list.append('Чёрная Вдова')

Аналогично сделано в современных языках программирования. Например, в C ++ у std::vector есть метод size(), который работает за O(1).

Однако, можно реализовать массив, длина которого не хранится в специальной переменной. Чтобы вычислить длину массива, нужно пройтись по всем его элементам и посчитать их. Так как элементов n, сложность операции вставки составит O(n).

Какая сложность вставки нового элемента в начало массива?

O(n)

Да! Разберёмся, почему.

O(1)

O(n²)

Рассмотрим пример.

Рита обычно составляет список дел на день, чтобы ничего не забыть. Она записывает дела в том порядке, в каком планирует ими заниматься. Вот планы на сегодня:

Скопировать кодPYTHON
list_of_tasks = ["Полить цветы", "Приготовить завтрак", "Пойти на работу", "Сходить в магазин", "Позвонить бабушке"]

Но тут ей звонит Алла и просит срочно помочь разобраться с багом в коде. Рита, конечно, решает отодвинуть все свои дела, чтобы не бросать подругу в беде.

Теперь у Риты новое дело — помочь Алле. Оно должно стоять в начале списка.

Но для этого нужно передвинуть каждый элемент на одну ячейку вправо. Сложность этого алгоритма будет O(n), где n — количество элементов в массиве.

Почему для добавлении элемента в конец массива требуется меньше операций, чем в начало?

Представьте, что Рита записывает список дел на листе бумаги. В конец легко добавить новый пункт, а в начале места уже нет. Значит, чтобы создать список с новым первым пунктом, придётся всё переписывать. Также и компьютеру нужно переместить каждый из уже существующих элементов. Поэтому сложность вставки элемента в начало массива составляет O(n).

А что, если нужно вставить элемент в произвольное место массива? Конечно, вставка в начало и конец — частные случаи этого примера. Вставка элемента в начало — худший случай. Сложность этой операции О(n). Добавление элемента в конец — лучший случай. И его сложность О(1).

Поиск элемента

Недавно на встрече Гоше пришла в голову классная идея. Он записал её в блокнот, чтобы позже обдумать. Идею Гоша забыл, и где именно в блокноте он её записал, тоже. Чтобы найти запись, можно просмотреть каждую страницу с начала. Запись может оказаться прямо на первой странице. Но возможно, Гоше придётся пролистать их все. Сложность операции поиска в лучшем случае O(1), а в худшем — O(n).

Но если нужно найти не конкретную запись в блокноте, а все страницы, где что-то записано? В этом случае придётся просмотреть каждую страницу. Тогда сложность будет O(n).

Со сложностью операции удаления вы разберётесь самостоятельно, выполняя задания. Будет ничуть не сложнее, чем вставка и поиск. У вас всё получится!

Гоша и его руководитель искали программиста в команду. Дело было срочное, и они решили взять первого же кандидата, который закончил курс Яндекс.Практикума «Алгоритмы и структуры данных». Какая будет сложность алгоритма поиска человека на вакансию в худшем случае?

O(1)

Нужно найти человека, который закончил курс Яндекс.Практикума. В худшем случае его может вообще не оказаться среди кандидатов. Тогда придётся провести n собеседований. Таким образом, сложность алгоритма будет O(n).

O(n²)

O(n)

А в лучшем случае?

O(1)

O(n²)

O(n)

За несколько месяцев вся команда так хорошо работала, что появилось много новых проектов. Компании нужны новые разработчики, и она может себе позволить нанять много новых сотрудников. Руководство решило, что теперь возьмёт всех претендентов, которые закончили курс Яндекс.Практикума по алгоритмам.

Какая теперь будет сложность в худшем случае?

O(1)

O(n²)

O(n)

А в лучшем?

O(1)

Чтобы взять взять всех кандидатов, которые окончили курс Яндекс.Практикума, придётся провести собеседование с каждым. То есть сложность алгоритма будет O(n) и в лучшем, и в худшем случае.

O(n²)

O(n)

У Риты скоро день рождения, и она составляет список гостей. Когда в нём стало уже десять имён, Рита вспомнила свою соседку Катю. Та приглашала её к себе на день рождения. Рита решает добавить Катю в список. Какая будет сложность операции?

Предположим, вы пишете на Python или используете vector в С++.

O(1)

O(n²)

O(n)

Как хранятся элементы массива в памяти компьютера?

В последовательных ячейках памяти

В произвольном порядке

Какая сложность операции удаления элемента из начала массива?

O(1)

Нет, правильный ответ — O(n).

Чтобы удалить элемент, его нужно сначала найти. Сложность операции поиска элемента в массиве в худшем случае составляет O(n). Но искомый элемент находится в начале массива, поэтому нужна всего одна операция. Найдя элемент, его нужно удалить. Для этого передвинем все элементы, которые идут следом за удалённым, на одну ячейку влево. Таких элементов n-1, то есть нужно будет n-1 раз передвинуть элемент влево. А сложность такой операции O(n). Суммарная сложность алгоритма –– О(n).

O(n²)

O(n)

А из конца массива?

Предположим, вы пишете на Python или используете vector в С++.

O(1)

O(n²)

O(n)

Отлично. Теперь решите задачи С и D из контеста.