Хеш-таблицы и приближённые алгоритмы (10 декабря)
- Хеширование
- Списки: амортизированное время O(1), время одной операции до O(logn) (матожидание максимума). Как уменьшить?
- Открытая адресация: [code]
- Удаление из хеш-таблицы с открытой адресацией
- Тестирование скорости работы открытой адресации [code] (0.22 sec vs 1.05 sec)
- Приближённые алгоритмы
- 2-приближённый алгоритм построения минимального вершинного покрытия
- Не существование приближения для задачи коммивояжёра в графах без неравенства треугольника
- Жадное приближение для bin packing (FFD, BFD, реализация set-ом)
- Жадное приближение для shortest superstring