В чем суть selection алгоритмов?

Question

[Тарасов Константин]

Собственно, вот здесь описана проблема и разные алгоритмы. Но я хоть убей не могу понять, для чего они вообще нужны, в плане - а что мы ищем то? К-тые элементы какие-то. В качестве примера даны поиск минимума, максимума и середины, но причем тут К вообще?

Answer 1

[Сергей Протько]

Задача на поиск k-ого элемента по величине это.

Представьте себе отсортированный по возрастанию список чисел от 1 до n. Вам нужно найти минимум - это первый элемент, то есть k = 0. Вам нужно найти максимальный элемент - k = n-1. Медиану найти нужно - k = n/2 (целочисленное деление, дробная часть просто выкидывается). Вроде как все довольно просто...

А теперь представим что список не отсортирован, что там есть повторяющиеся элементы и т.д. Вот... Можно отсортировать список за O(n log(n)) например, а потом сделать выборки по индексам. А можно за O(n) просто найти...

Comments

[Тарасов Константин]

Т.е. нам нужно найти элемент, который, если бы массив\список был отсортирован, находился бы в нем на k-том месте, так?

[Сергей Протько]

@saroff что-то типа того. Только насколько я понимаю массив должен быть отсортирован и без повторений.

Answer 2

[Roman Zhak]

Речь идет о порядковых статистиках - это просто упорядоченная выборка по возрастаю. Следовательно, задача сводится к элементарной сортировке и выбора нужного по счету элемента.
Максимальное и минимальное значения приводятся, потому что очевидно, какие места они занимают в отсортированном массиве.