я получил следующий вопрос в книге алгоритмы:случайная сортировка слиянием
Предположим, что сортировка слиянием реализована возможность разделить файл на случайном месте, а затем ровно посередине. Сколько сравнений будет использоваться таким методом для сортировки n элементов в среднем?
Спасибо.
Чтобы направить вас к ответу, рассмотрим эти более конкретные вопросы:
Предположим, что раскол всегда на 10%, или 25%, или 75%, или на 90%. В каждом случае: каково влияние на глубины рекурсии? Сколько сравнений должно быть на уровне рекурсии?
Я частично согласен с @Armen, они должны быть сопоставимы.
Но: рассмотрите случай, когда они разделены посередине. Чтобы объединить два списка длин n, нам понадобятся 2*n - 1 сравнения (иногда меньше, но мы будем считать это исправлено для простоты), каждый из которых производит следующее значение. Там будет log2(n) уровней слияний, что дает нам приблизительно n*log2(n) сравнения.
Теперь с учетом случайного раздвоением случая: Максимальное количеством comparations, необходимым для объединения списка длины n1 с одной длиной n2 будет n1 + n2 - 1. Howerer, среднее число будет близко к нему, потому что даже для самого несчастливого раскола 1 и n-1 нам понадобится в среднем n/2. Поэтому мы можем считать, что стоимость слияния на уровне будет такой же, как в четном случае.
Разница в том, что в случайном случае количество уровней будет больше, и мы можем считать, что n для следующего уровня будет max(n1, n2) вместо n/2. Это max(n1, n2) будет иметь тенденцию быть 3*n/4, что дает нам приближенную формулу
n*log43(n) // where log43 is log in base 4/3
, что дает нам
n * log2(n)/log2(4/3) ~= 2.4 * n * log2(n)
Этот результат по-прежнему больше, чем правильный один, потому что мы не учитывали, что маленький список будет иметь меньше но он должен быть достаточно близко. Я полагаю, что правильный ответ будет число comparations в среднем удвоит
Вы можете получить верхнюю границу 2п * H_ {п - 1} < = 2n пер п, используя тот факт, что слияние двух списков общая длина n стоит не более n сравнений. Анализ аналогичен анализу рандомизированных quicksort (см. http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf).
Прежде всего предположим, что мы разделим список длины n на 2 списка L и R. Мы будем заряжать первый элемент R для сравнения со всеми элементами L, а последний элемент L для сравнения против все элементы R. Даже если это не могут быть точные сравнения, которые выполняются, общее количество сравнений, которые мы взимаем, равно n, как требуется.
Это ручка одного уровня рекурсии, но как насчет остального? Мы продолжаем концентрироваться только на сравнениях «справа налево», которые происходят между первым элементом R и каждым элементом L на всех уровнях рекурсии (по симметрии это будет половина фактического ожидаемого общего).Вероятность того, что j-й элемент сравнивается с i-м элементом, равна 1/(j - i), где j> i. Чтобы увидеть это, обратите внимание, что элемент j сравнивается с элементом i точно, когда он является первым элементом, выбранным как «элемент расщепления» из множества {i + 1, ..., j}. То есть элементы i и j разбиваются на два списка, как только список, в котором они находятся, разбивается на некоторый элемент из {i + 1, ..., j}, а элемент j заряжается для сравнения с i точно, когда элемент j является элементом, выбранным из этого множества.
Таким образом, ожидаемое общее количество сравнений с участием j не превышает H_n (то есть 1 + 1/2 + 1/3 ..., где число членов не более n - 1). Суммирование по всем возможным j дает n * H_ {n - 1}. Это только учитывало сравнение «справа налево», поэтому окончательная верхняя граница равна 2n * H_ {n - 1}.