Участник:Shersh/Тикеты по конспектам year2013 — различия между версиями
Shersh (обсуждение | вклад) (Новая страница: «== Амортизационный анализ == * Амортизационный анализ * Саморасширяющийся массив * [[Ма...») |
Shersh (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | == Амортизационный анализ == | + | Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела. |
| + | |||
| + | == 1. Амортизационный анализ == | ||
* [[Амортизационный анализ]] | * [[Амортизационный анализ]] | ||
* [[Саморасширяющийся массив]] | * [[Саморасширяющийся массив]] | ||
| Строка 12: | Строка 14: | ||
* [[Счетчик Кнута]] | * [[Счетчик Кнута]] | ||
| − | == Приоритетные очереди == | + | == 2. Приоритетные очереди == |
* [[Двоичная куча]] | * [[Двоичная куча]] | ||
| Строка 22: | Строка 24: | ||
* [[Куча Бродала-Окасаки]] | * [[Куча Бродала-Окасаки]] | ||
| − | == Система непересекающихся множеств == | + | == 3. Система непересекающихся множеств == |
* [[СНМ (наивные реализации) | Наивные реализации]] | * [[СНМ (наивные реализации) | Наивные реализации]] | ||
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] | * [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]] | ||
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] | * [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]] | ||
| − | == Поисковые структуры данных == | + | == 4. Поисковые структуры данных == |
* [[Упорядоченное множество]] | * [[Упорядоченное множество]] | ||
* [[Дерево поиска, наивная реализация]] | * [[Дерево поиска, наивная реализация]] | ||
| Строка 43: | Строка 45: | ||
* [[Сверхбыстрый цифровой бор]] | * [[Сверхбыстрый цифровой бор]] | ||
| − | == Дерево отрезков == | + | == 5. Дерево отрезков == |
* [[Статистики на отрезках. Корневая эвристика]] | * [[Статистики на отрезках. Корневая эвристика]] | ||
| Строка 53: | Строка 55: | ||
* [[Сжатое многомерное дерево отрезков]] | * [[Сжатое многомерное дерево отрезков]] | ||
| − | == Дерево Фенвика == | + | == 6. Дерево Фенвика == |
* [[Дерево Фенвика]] | * [[Дерево Фенвика]] | ||
* [[Встречное дерево Фенвика]] | * [[Встречное дерево Фенвика]] | ||
| Строка 59: | Строка 61: | ||
* [[Многомерное дерево Фенвика]] | * [[Многомерное дерево Фенвика]] | ||
| − | == Хеширование == | + | == 7. Хеширование == |
* [[Хеш-таблица]] | * [[Хеш-таблица]] | ||
* [[Разрешение коллизий]] | * [[Разрешение коллизий]] | ||
| Строка 68: | Строка 70: | ||
* [[Универсальное семейство хеш-функций]] | * [[Универсальное семейство хеш-функций]] | ||
| − | == [[Сортировка]] == | + | == 8. [[Сортировка]] == |
* [[Сортировка выбором]] | * [[Сортировка выбором]] | ||
* [[Сортировка пузырьком]] | * [[Сортировка пузырьком]] | ||
| Строка 87: | Строка 89: | ||
* [[Timsort]] | * [[Timsort]] | ||
| − | == Сортирующие сети == | + | == 9. Сортирующие сети == |
* [[Сортирующие сети]] | * [[Сортирующие сети]] | ||
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | * [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]] | ||
| Строка 94: | Строка 96: | ||
* [[Сеть Бетчера]] | * [[Сеть Бетчера]] | ||
| − | == Алгоритмы поиска == | + | == 10. Алгоритмы поиска == |
* [[Целочисленный двоичный поиск]] | * [[Целочисленный двоичный поиск]] | ||
* [[Вещественный двоичный поиск]] | * [[Вещественный двоичный поиск]] | ||
Версия 18:29, 15 апреля 2014
Тикеты индексируются как "X-Y", где X — номер раздела, Y — номер конспекта внутри раздела.
Содержание
1. Амортизационный анализ
- Амортизационный анализ
- Саморасширяющийся массив
- Массив с увеличением/уменьшением размера
- Список
- Стек
- Очередь
- Персистентный стек
- Персистентная очередь
- Персистентный дек
- Мажорирующий элемент
- Счетчик Кнута
2. Приоритетные очереди
- Двоичная куча
- Биномиальная куча
- Фибоначчиева куча
- Левосторонняя куча
- Тонкая куча
- Толстая куча на избыточном счетчике
- Куча Бродала-Окасаки
3. Система непересекающихся множеств
4. Поисковые структуры данных
- Упорядоченное множество
- Дерево поиска, наивная реализация
- АВЛ-дерево
- 2-3 дерево
- B-дерево
- Красно-черное дерево
- Декартово дерево
- Декартово дерево по неявному ключу
- Splay-дерево
- Рандомизированное бинарное дерево поиска
- Дерево ван Эмде Боаса
- Список с пропусками
- Fusion tree
- Сверхбыстрый цифровой бор
5. Дерево отрезков
- Статистики на отрезках. Корневая эвристика
- Дерево отрезков. Построение
- Реализация запроса в дереве отрезков сверху
- Реализация запроса в дереве отрезков снизу
- Несогласованные поддеревья. Реализация массового обновления
- Многомерное дерево отрезков
- Сжатое многомерное дерево отрезков
6. Дерево Фенвика
- Дерево Фенвика
- Встречное дерево Фенвика
- Дерево Фенвика для некоммутативных операций
- Многомерное дерево Фенвика
7. Хеширование
- Хеш-таблица
- Разрешение коллизий
- Хеширование кукушки
- Идеальное хеширование
- Перехеширование. Амортизационный анализ
- Фильтр Блума
- Универсальное семейство хеш-функций
8. Сортировка
- Сортировка выбором
- Сортировка пузырьком
- Сортировка вставками
- Сортировка Шелла
- Сортировка кучей
- Быстрая сортировка
- Сортировка слиянием
- Cортировка слиянием с использованием O(1) дополнительной памяти
- Теорема о нижней оценке для сортировки сравнениями
- Сортировка подсчетом
- Сортировка подсчетом сложных объектов
- Цифровая сортировка
- Карманная сортировка
- Поиск k-ой порядковой статистики
- Поиск k-ой порядковой статистики за линейное время
- Сортировка Хана
- Timsort
9. Сортирующие сети
- Сортирующие сети
- Проверка сети компараторов на то, что она сортирующая. 0-1 принцип
- Сортировочные сети с особыми свойствами
- Сортирующие сети для квадратичных сортировок
- Сеть Бетчера
