Алгоритмы и Структуры данных
Big O
- for - O(N)
- recursion - O(log(N))
- for for -
O(n^2)
Список
Операции
| Операция | Сложность |
|---|---|
| Обращение по индексу | O(1) |
| Поиск | O(N) |
| Вставка/удаление в конец | O(1) |
| Вставка/удаление по индексу | O(N) |
Как устроен
- Список - сишный массив/вектор - набор ячеек в памяти фиксированного размера
- Когда добавляется новый элемент, а буфер кончился, то происходит копирование и расширение массива
List Comprehension
- Итерация по компрехеншену медленнее цикла фор
- Создание через компрехеншен медленнее чем функция лист
Хеш-таблицы
Операции
| Операция | Сложность |
|---|---|
| Поиск | O(1) |
| Вставка | O(1) |
Коллизии
- Когда 2 ключа имеют одинаковый хеш
- Как быть
- Хеш-цепочки
- Открытая адресация
- Линейное пробирование
- Квадратичное пробирование
- Двойное хеширование
Хеш-цепочки
- Создаем массив с capacity
- При коллизии для хеша храним связный список
- Дальше последовательный поиск
- Чтобы цепочки не разрастались, при вставке иногда происходит расширение массива и перебалансировка
- Оптимизация: хранить ключи не в фикс. массиве, а в связном списке
Открытая адресация
- (Линейное) Пробирование - если коллизия, то суем в соседнюю ячейку (i + 1, i + 1, i + 1)
- Если пробирований много, то расширяем массив и перебалансируем
- Квадратичное Пробирование - шаг всегда увеличивается (i + 1, i + 2, i + 3)
- Двойное Хеширование - для след элемента используем не шаг, а еще одну хеш функцию
- Поиск - до первой пустой ячейки
- При удалении сдвигаем ячейки или помечаем что ячейка удалена
Что используется в Python
- Квадратичное Пробирование