Порядковые статистики (Темы на автомат)

Порядковые статистикиСреднее время для порядковых статистикАдоньева Вера, группа 17133Задача нахождения k-го наименьшего элемента в n-элементнойпоследовательности• Упорядочить эту последовательность и взять k-й элемент. Этопотребует log сравнений• Используя другой алгоритм найти k-й наименьший элемент за шагов3579191483641713457917193648procedure ВЫБОР , :1. if < 140 thenbegin2.упорядочить 3.return k-й наименьший элемент в endelsebegin!4.разбить на5.6.7.при этом останется не более четырех неиспользованных элементов;упорядочить каждую 5-элементную последовательность;пусть - последовательность медиан этих 5-элементных множеств;8.

← ВЫБОР9.10."последовательностей по 5 элементов в каждой;#$, ;пусть % , $ и & - последовательности элементов из , соответственно меньших, равных и больших ;if % ≥ then return ВЫБОР , %else11.if % + $ ≥ then return 12.else return ВЫБОР − % − $ , &end4, 5, 6, 7, 8...9:7, 9:6, 9:5, 9:4, 9"!4, . . . , ;ТеоремаПриведенный алгоритм находит -й наименьший элемент в-элементной последовательности за время .Доказательство:() – время, затрачиваемое на выбор -го наименьшего элемента.Получаем: ! ≥ 3Аналогично, & ≥ 3! ≤ − & ≤ −& ≤ − ! ≤ −! $−2 ≥# %! $# %&$!'&$!'&$!'−2 ≥−6 =−6 =($!'($!'−6&$!'−6+6+6 1 , ≤ 1397() ≤ 5 ++ 6 + , ≥ 140510Докажем, что для некоторого достаточно большого и для всех > 0, ≤ .Предположим, что выполняется для некоторого достаточнобольшого и для всех < 140.Константа такая, что линейная составляющая ≤ для всех>079 ≤++ 6 + ≤+ 7 + 51010= + − + 7 + 10 + −)$!'+ 7 + ≤ , если −Что эквивалентно ≥!'*$$ +('или!'+ 7 + ≤ 0при > 70Мы предположили, что > 140,То есть мы доказали, что)$$$ +('≤ 2, ≥ 20 ≤ ≤ 20Пусть = ! , # , .

. . , $ - множество из n различных элементов,а T – дерево решений какого-нибудь алгоритма для нахожденияk-ого наименьшего элемента в S. Каждый пусть p в T определяеттакое отношение , на S, что - , . , если два различных элемента- и . сравниваются в некотором узле, лежащем на p, и врезультате этого сравнения либо - < . , либо .

≤ - . Пусть ,/ транзитивное замыкание отношения , .Транзитивным замыканием отношения называется такоеотношение / , что / тогда и только тогда, когда существуетпоследовательность истинных утверждений вида ! # , # & , . . ., 0+! 0 , где ≥ 2, = ! , = 0 .ЛеммаЕсли на пути выясняется, что ! является k-м наименьшимэлементом в , то для любого ≠ , 1 ≤ ≤ , либо " #$ ! ,либо ! #$ " .Доказательство:Допустим, что некоторый элемент % не связан с ! отношением #$ .Пусть & = ' |' #$ % , ( = ' |% #$ ' и в ) входят все остальныеэлементы из .

По % и ! предположению принадлежат ) .Если ' – произвольный элемент в & (соответственно в ( ) и " #$ '(соответственно ' #$ " ), то в силу транзитивности " такжепринадлежит & (соответственно ( ). Можно построить линейныйпорядок R, совместимый с #$ , что все элементы из & предшествуювсем элементам из ) , которые предшествуют всем элементам из ( .465По предположению элемент 1 не связан отношением ,/ ни содним элементом из & . Допустим, что 1 предшествует 0 прилинейном порядке R, 1 0 . Тогда можно построить новыйлинейный порядок R’, совпадающий с R во всем, кроме того, что 1следует за 0 .

Отношение R также совместимо с , . Для каждогопорядка R и R’ можно найти различные элементы,удовлетворяющие соответственно R или R’. Но 0 не может бытьk-м наименьшим элементом в обоих случаях, так как в R’ элементу0 предшествует на один элемент меньше чем в R.Поэтому получаем, что если какой-то элемент из не связан с 0отношением ,/ , то дерево T не может правильно выбратьнаименьший элемент из .Аналогично случай 0 1 .Доказательство окончено.ТеоремаЕсли - дерево решений, выбирающее k-й наименьшийэлемент в множестве , = , то глубина любого листадерева не меньше − 1.Доказательство:Рассмотрим путь в от корня к листу.

По предыдущей леммелибо - ,/ 0 , либо 0 ,/ - для каждого ≠ , где 0 – элемент,выбранный в качестве k-ого наименьшего. Для элемента - , ≠ ,определим ключевое сравнение как первое сравнение на ,содержащее - и такое, что выполнено одно из условий:1) - сравнивается с 02) - сравнивается . , - , . и .

,/ 03) - сравнивается . , . , - и 0 ,/ .Ключевое сравнение для - – это первое сравнение, из которогоможно определить, предшествует элемент - элементу 0 илиследует за ним.Понятно, что всякий элемент - , кроме 0 , обладает ключевымсравнением; иначе не выполнилось бы ни - ,/ 0 , ни 0 ,/ - .Никакое сравнение не может быть ключевым для обоихсравниваемых элементов.

Так как в ключевые сравнения должнывовлекаться − 1 элементов, то длина пути должна быть неменьше − 1.Доказательство окончено.СледствиеНахождение k-го наименьшего элемента в требует неменьше − 1 сравнений как в среднем, так и в худшемслучае.1.2.3.4.5.6.procedure ВЫБОР , :if = 1 then return единственный элемент множества elsebeginслучайно выбрать элемент из ;пусть ! , # и & - последовательности элементов из ,соответственно меньших, равных и больших ;if ! ≥ then return ВЫБОР , !elseif ! + # ≥ then return else return ВЫБОР − ! − # , &end><=ТеоремаСреднее время работы приведенного алгоритма линейно.Доказательство:Чтобы проанализировать ожидаемое время работы алгоритмаоценивается сверху математическое ожидание времени работы .* = I & ∪ ( содержит ровно элементов1 * =Если * = 1, то размеры двух подмасивов, к которым может произойтирекурсивное обращение − 1 и − .Другими словами элемент , выбранный в строке 2, является -мнаименьшим элементом в .

Число может принимать значения 1, 2, . .., n равновероятно. Если > , то ВЫБОР вызывается дляпоследовательности, состоящей из − 1 элементов, а если < , то дляпоследовательности, состоящей из − элементов.Если четно, то каждое слагаемое от $⁄# до ( − 1)появляется в сумме ровно дважды. Если же нечетно, то дваждыпоявляются все слагаемые, кроме $⁄# , которое добавляетсялишь один раз. Таким образомТеперь покажем, что = ()Предположим, что ≤ для некоторой константы , и чтодля меньших какой-то константы справедливо = 1 , этаконстанта будет найдена позже.Выберем также константу , чтобы чтобы ограничить сверхунерекурсивную составляющую.Спасибо за внимание!.