Урок 0: почему выбор структуры данных имеет значение?

Представьте телефонный справочник с миллионом имён, перечисленных в совершенно случайном порядке. Чтобы найти номер одного человека, вам пришлось бы перелистывать страницу за страницей, пока вы не наткнётесь на нужное имя — в среднем около половины страниц, а в худшем случае все страницы. Тот же сам

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

структура данных: Организованный способ хранить информацию так, чтобы к ней можно было обращаться, искать в ней и обновлять её.
поиск: Операция нахождения конкретного элемента внутри набора данных.
линейный перебор: Проверка элементов один за другим по порядку, пока не найдётся нужный — чем больше элементов, тем дольше ожидаемое время.
прямой доступ: Переход почти сразу в нужное место, без прохождения через каждый другой элемент по пути.