Блог

Проблема здесь заключается в том, чтобы уменьшить среднее количество сравнений, необходимых при сортировке выбора.

Я читаю статью об этом, и вот фрагмент текста:

В более общем случае выборка S’ из s элементов выбирается из n элементов. Пусть «дельта» будет некоторым числом, которое мы выберем позже, чтобы минимизировать среднее число сравнений, используемых процедурой. Мы находим (v1 = (k * s) / (n — дельта))-й и (v2 = (k * * s) / (n дельта))-й наименьшие элементы в S’. Почти наверняка k-й наименьший элемент в S будет находиться между v1 и v2, поэтому мы остаемся с проблемой выбора (2 * дельта) элементов. С низкой вероятностью k-й наименьший элемент не попадает в этот диапазон, и нам предстоит проделать значительную работу. Однако при хорошем выборе s и дельты мы можем гарантировать по законам вероятности, что второй случай не окажет отрицательного влияния на общую работу.

Я не следую приведенному выше тексту. Может кто-нибудь, пожалуйста, объясните мне с примерами. Как автор сократил до 2 * дельта-элементов? И откуда он знает, что существует низкая вероятность того, что элемент не попадает в эту категорию.

Спасибо!

Основой идеи является то, что обычный алгоритм выбора имеет линейную сложность во время выполнения, но на практике работает медленно. Нам нужно отсортировать все элементы в группы по пять и рекурсивно выполнить еще больше работы. O(n) но со слишком большой константой. Таким образом, идея состоит в том, чтобы уменьшить количество сравнений в алгоритме выбора (не обязательно сортировка выбора). Интуитивно это то же самое, что и в базовой статистике; если я беру выборочное подпространство достаточно большой пропорции, вполне вероятно, что распределение данных в подпространстве адекватно отражает данные во всем пространстве.

Итак, если я ищу k-е число в наборе размером один миллион, я мог бы вместо этого взять, скажем, 10 000 (уже одну сотую размера), который все еще достаточно велик, чтобы быть хорошим представлением глобального распределения, и искать k / 100-е число. Это простое масштабирование. Итак, если пространство было 10, и я искал 3-е, это все равно, что искать 30-е из 100 или 300-е из 1000 и т. Д. По сути k/S = k'/S' (где мы ищем k-е число в S, и мы переводим его в k-е число в S’ нашем подпространстве) и, следовательно k' = k*S'/S , которое должно выглядеть знакомо, поскольку в процитированном вами тексте S’ обозначается через s, а S через n, и это та же самая дробь, которая указана в кавычках.

Теперь, чтобы учесть статистические колебания, мы не предполагаем, что подпространство будет идеальным представлением распределения данных, поэтому мы допускаем некоторые колебания, а именно дельта. Скажем, давайте найдем k-й-дельта и k-й дельта элементы в S ‘, и тогда мы можем с большой уверенностью (т. Е. С высокой математической вероятностью) сказать, что k-е значение из S находится в интервале (k-я дельта, k-я дельта).

Чтобы завершить все это, мы выполняем эти два выбора для S ‘, затем разделяем S соответственно, и теперь делаем [обычный] выбор на гораздо меньшем интервале в разделе. В итоге это оказывается почти оптимальным для элементов за пределами интервала, потому что мы не делаем для них выбор, а только разделяем их. Таким образом, процесс выбора происходит быстрее, потому что мы уменьшили размер проблемы с S до S ‘.