saroff
@saroff
Enterprise Java Developer

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

Собственно, вот здесь описана проблема и разные алгоритмы. Но я хоть убей не могу понять, для чего они вообще нужны, в плане - а что мы ищем то? К-тые элементы какие-то. В качестве примера даны поиск минимума, максимума и середины, но причем тут К вообще?
  • Вопрос задан
  • 2237 просмотров
Пригласить эксперта
Ответы на вопрос 2
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
Задача на поиск k-ого элемента по величине это.

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

А теперь представим что список не отсортирован, что там есть повторяющиеся элементы и т.д. Вот... Можно отсортировать список за O(n log(n)) например, а потом сделать выборки по индексам. А можно за O(n) просто найти...
Ответ написан
romanzhak
@romanzhak
Mathematician
Речь идет о порядковых статистиках - это просто упорядоченная выборка по возрастаю. Следовательно, задача сводится к элементарной сортировке и выбора нужного по счету элемента.
Максимальное и минимальное значения приводятся, потому что очевидно, какие места они занимают в отсортированном массиве.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы