КАК РАБОТАЕТ ПАМЯТЬ
Память компьютера состоит из множества ячеек, в каждой из которых
может храниться одно значение.
Если нужно сохранить сразу несколько значений, можно воспользоваться
массивом или связанным списком.
МАССИВЫ И СВЯЗАННЫЕ СПИСКИ
Массив
Все значения массива хранятся в памяти друг за другом, непрерывно.
Сложности с добавлением новых элементов - следующая ячейка может
быть уже занята, придется выделять новое место для увеличившегося
массива в памяти.
Возможное решение: бронирование запасных мест.
Преимущество: заранее известен адрес каждого элемента в памяти
(произвольный доступ). Легко получить любой элемент массива (по индексу).
| Операция | Время выполнения |
|---|---|
| Чтение | O(1) |
| Вставка | O(n) |
| Удаление | O(n) |
Связанный список
Решает проблему добавления новых элементов, так как элементы списка
могут храниться в памяти где угодно. Просто в каждом элементе хранится
ссылка на следующий.
Появляется другая проблема: затруднен доступ к элементу списка по его
индексу (последовательный доступ).
| Операция | Время выполнения |
|---|---|
| Чтение | O(n) |
| Вставка | O(1) |
| Удаление | O(1) |
СОРТИРОВКА ВЫБОРОМ
Алгоритм сортировки массива значений, при котором просматриваются все значения,
среди них выбирается наибольшее/наименьшее и помещается в новый отсортированный
массив. С каждым разом количество элементов в исходном массиве сокращается,
а в новом - увеличивается на 1.
Время выполнения: O(n2).
Алгоритм просматривает весь список (O(n)) n раз (O(n)). На самом деле,
список каждый раз сокращается, и правильнее было бы сказать, что время
выполнения алгоритма составляет O(n * 1/2 * n), но константы в O-большом игнорируются.
Пример сортировки выбором в этой главе