Категория:Учебный курс «Алгоритмы и структуры данных»: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 41: | Строка 41: | ||
:* [[Декартово дерево]] | :* [[Декартово дерево]] | ||
:* [[Расширения декартова дерева]] | :* [[Расширения декартова дерева]] | ||
: | : Структуры данных для задач RSQ/RMQ | ||
:* Sqrt-декомпозиция | |||
:* Дерево Фенвика | |||
:* Дерево отрезков | |||
:* [[Sparse table]] | |||
| | | | ||
;3. Алгоритмы для работы с графами | ;3. Алгоритмы для работы с графами | ||
| Строка 50: | Строка 54: | ||
:* [[Циклы в графе. Двудольность]] | :* [[Циклы в графе. Двудольность]] | ||
:* [[Компоненты связности]] | :* [[Компоненты связности]] | ||
:* [[Мосты | :* [[Мосты. Компоненты рёберной двусвязности]] | ||
:* [[Точки сочленения. Компоненты вершинной двусвязности]] | |||
:* [[Топологическая сортировка]] | :* [[Топологическая сортировка]] | ||
:* [[Компоненты сильной связности. Алгоритм Косараю-Шарира]] | :* [[Компоненты сильной связности. Алгоритм Косараю-Шарира]] | ||
: Кратчайшие пути из одной вершины | : Кратчайшие пути из одной вершины | ||
:* [[Поиск в ширину]]<sup>''O(V+E)''</sup> | :* [[Поиск в ширину]]<sup>''O(V+E)''</sup> | ||
:* [[Алгоритм Дейкстры]]<sup>''O(V<sup>2</sup>+E) | :* [[Алгоритм Дейкстры]]<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | ||
:* [[Алгоритм Форда-Беллмана]]<sup>''O(VE)''</sup> | :* [[Алгоритм Форда-Беллмана]]<sup>''O(VE)''</sup> | ||
:* Кратчайшие пути в ациклических орграфах<sup>''O(V+E)''</sup> | :* Кратчайшие пути в ациклических орграфах<sup>''O(V+E)''</sup> | ||
| Строка 63: | Строка 68: | ||
: Минимальное остовное дерево | : Минимальное остовное дерево | ||
:* [[Алгоритм Краскала]]<sup>''O(ElogV)''</sup> | :* [[Алгоритм Краскала]]<sup>''O(ElogV)''</sup> | ||
:* [[Алгоритм Прима]]<sup>''O(V<sup>2</sup>+E), O( | :* [[Алгоритм Прима]]<sup>''O(V<sup>2</sup>+E) или O(ElogV)''</sup> | ||
: Наименьший общий предок | |||
:* [[Метод двоичного подъёма]]<sup>''O(NlogN), O(logN)''</sup> | |||
:* [[Сведение LCA к RMQ и RMQ к LCA]] | |||
:* [[Алгоритм Тарьяна (offline)]]<sup>''O(N), O(1)''</sup> | |||
; Будущие разделы | ; Будущие разделы | ||
: | : | ||
Версия от 14:01, 23 августа 2014
|
|
© В. А. Фолунин, УлГТУ, 2012–2014
Подкатегории
В этой категории отображается 12 подкатегорий из имеющихся 12.
Страницы в категории «Учебный курс «Алгоритмы и структуры данных»»
Показаны 4 страницы из 4, находящихся в данной категории.