Найти k-й по величине элемент, не сортируя весь массив. делает это в среднем за линию.
Ключевые тезисы
- — , спускающаяся только в нужную половину: O(n) в среднем.
- гарантирует линейное время в худшем случае ценой большой константы.
- размера k решает задачу «топ-k» за O(n log k) и работает на потоке.
Видеолекции
Записи университетских курсов, где эта тема звучит. Тайм-кодов у них нет, поэтому открываются они с начала.
Связанные темы
Структуры данных
Hash Tables85%
Хеш-таблицы · Алгоритмы и структуры данныхДоступ по ключу за константу в среднем. Основа словарей и множеств — и структура, на которой держится большая часть повседневного кода.
Arrays, Lists, Stacks and Queues85%
Массивы, списки, стеки и очереди · Алгоритмы и структуры данныхЧетыре базовых способа хранить последовательность. Отличаются не тем, что умеют, а тем, что у них дёшево, а что дорого.
Trees and Heaps85%
Деревья и кучи · Алгоритмы и структуры данныхИерархические структуры, дающие логарифмические операции: двоичное дерево поиска для упорядоченных запросов, куча — для быстрого минимума.
Sorting Algorithms85%
Сортировки · Алгоритмы и структуры данныхБыстрая, слиянием, пирамидальная — три способа упорядочить данные за O(n log n) с разными свойствами по памяти, устойчивости и худшему случаю.
Caching85%
Кеширование · Системный дизайн ML-сервисовНе считать то, что уже посчитано: кеш предсказаний, признаков и эмбеддингов.
Тема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.