общее количество сравнений, необходимых для объединения отсортированных файлов

Question

С учетом 4 отсортированных файлов, содержащих 15,3,9 и 8 записей, каково общее число сравнений, необходимых для объединения их в один отсортированный файл?

Предположим, что мы используем шаг слияния (из слиянияsort) для этого.

Я знаю, что для выполнения шага объединения требуется O (N) времени.Но сколько сравнений это делает?

Answer 1

Если вы предполагаете, что используете шаг слияния из типичной сортировки слиянием, это означает, что вы можете объединять только 2 списка за раз, что упрощает задачу.Нам нужно как минимум 3 слияния, чтобы превратить 4 списка в 1. Мы могли бы разделить списки, но это выбрасывает информацию, и в конечном итоге нам нужно только объединить их, поэтому я сомневаюсь, что это помогает (без доказательстваэто).

Единственный вопрос, то, какой порядок объединения списков.Наихудшее число сравнений для объединения в общей сложности k элементов из двух списков - k-1 [*], поэтому мы хотим минимизировать общее количество элементов во всех слияниях.Я думаю (опять же, не доказывая этого), что в этом случае это делается путем слияния попарно от наименьшего к наибольшему, то есть 8+3, затем 11+9, затем 20+15.Это всего 10+19+34 = 63 сравнений записей в худшем случае.

Менее хитрый выбор слияний, скажем 15+3 затем 8+9 затем 18+17, потребовал бы больше сравнений в худшем случае (67), но вам не нужно знать длину списков, прежде чем вы начнете.

[*] доказательство по индукции:

При k = 1 требуется 0 сравнений, посколькуу нас есть один пустой список и один список длиной 1.

Предположим, это верно для списков общей длины j (для некоторых j> = 1).Затем в худшем случае, чтобы объединить два отсортированных списка длиной j + 1, мы сначала сравниваем наименьшие элементы с обеих сторон, удаляем меньший и помещаем его в список вывода.Осталось только объединить то, что осталось в двух списках, то есть общей длины j.Мы можем сделать это в худших j-1 сравнениях по индуктивной гипотезе.Следовательно, всего j + 1 элементов требует в худшем случае j сравнений, что завершает индукцию.

Answer 2

Я думаю, что мы можем обобщить ответ примерно.Для n списков длиной k1, k2, ..., kn в обозначениях Big Oh наихудший случай ограничен O ((n-1) (k1 + k2 + k3 ... + kn)).Эта идея возникла у меня из вопроса о CLRS (вопрос 2-1 главы 2).

Answer 3

Наихудший случай слияния двух отсортированных списков имеет место в случае, когда оба списка остаются ненулевым в течение максимального количества времени . В этом случае с 15, 3, 9 и 8 элементами у нас есть 3 сравнения, чтобы найти наименьший элемент (4 элемента и выбор сортировки занимает 3 сравнения). В худшем случае представьте: у нас есть 3,3,3 и 3 элемента в каждом списке. До этого момента количество сравнений: (12 + 0 + 6 + 5) * 3 = 69. Теперь с остальными списками (3,3,3,3) ключей уменьшите их до (2,2,2,2) элементов (так 4 * 3 = 12 сравнений). Снова уменьшите (2,2,2,2) до (1,1,1,1), используя 4 * 3 = 12 сравнений. Теперь уменьшите (1,1,1,1) до (0,1,1,1) на 3 сравнения. Теперь уменьшите (0,1,1,1) до (0,0,1,1) на 2 сравнения. Теперь уменьшите (0,0,1,1) до (0,0,0,1), используя 1 сравнение. Теперь добавьте последний элемент в отсортированный список с 0 сравнениями. Отсюда общее сравнение: 69 + 12 + 12 + 3 + 2 + 1 + 0 = 99 сравнений.

Answer 4

общее количество сравнений, необходимых для двух файлов размером m, n равны

m + n - 1 

Таким образом, для выше мы требуем

15 + 3 -1 = 17 

8 + 9 -1 = 16

17 + 16 -1 = 32 

Answer 5

Если мы объединяем два списка, процедура объединения требует не более: n1 + n2 сравнений, где n1 и n2 - длина списков.

При наличии 4 списков общее количество будет зависеть от порядка, который мы используем в этом объединении: т.е. мы можем объединить list1 и list2, а затем объединить результат со списком3, а затем со списком4;или мы можем объединить list1 и list2, объединить list3 и list4, а затем объединить 2 результата.

В этом случае легко проверить, что это лучшая стратегия:

(list1 <-> list2) <-> (list3 <-> list4)          (<-> stands for merge)

Какое максимальное число сравнений?Легко вспомнить начальную формулу:

(15 + 3) + (9 + 8) + ((15+3) + (9+8)) = 18 + 17 + 18 + 17 = 70

Answer 6

Как и в ответе Му Цяо (несколько повторенный здесь для удобства), мы можем объединить списки, приняв наименьшее значение a, b, c, d на каждом шаге. Для этого требуется максимум 3 сравнения: сравнение a и b, сравнение c и d и сравнение минимума {a, b} и {c, d}. Мы можем легко увидеть, что это лучшее, что мы можем сделать, так как двух сравнений недостаточно.

Предположим, мы исчерпали один список. Предположим без ограничения общности, что этот список d. Теперь, чтобы сравнить a, b, c, мы можем сравнить a и b, а затем сравнить минимум или {a, b} с c. Мы можем видеть, что мы не можем добиться большего успеха, чем это, поскольку одного сравнения недостаточно.

Когда есть два списка, нам, очевидно, нужно ровно 1 сравнение, а когда есть один список, нам, очевидно, не нужны сравнения.

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

В этом случае будет не более 14+2+8+7 = 31 сравнений, прежде чем список будет исчерпан. Оттуда будет один список, истощенный для каждого обрабатываемого элемента. Таким образом, число сравнений в худшем случае равно 31*3 + 2 + 1 + 0 = 96.

Answer 7

Каждый шаг, когда нужно знать текущий наименьший элемент среди 4 файлов. Другими словами, нам нужно знать наименьший из четырех элементов a, b, c, d. Таким образом, наивный способ будет использовать три сравнения для каждого шага (a и b, c и d, меньшее из ab и cd). Таким образом, общее сравнение будет 3 * N (N - общее количество записей).