Почему итеративное слияние K-way O (nk ^ 2)?

k-way merge - это алгоритм, который принимает в качестве входных данных k отсортированные массивы, каждый из которых имеет размер n. Он выводит один отсортированный массив всех элементов.

Это достигается с помощью «слияния» подпрограмма центральная в алгоритме сортировки слиянием, чтобы объединить массив 1 в массив 2, а затем массив 3 в этот объединенный массив и так далее, пока все k массивов не будут объединены.

Я думал, что этот алгоритм O (kn), потому что алгоритм перебирает каждый из k массивов (каждый длиной n) один раз. Почему это O (NK ^ 2)?

 claudius08 апр. 2014 г., 22:47
Обход @Dejel по всем элементам займет O (nk). Используя кучу, мы можем получить O (nklogk). Можете ли вы рассказать о том, как достичь O (nlogk)?
 locojay29 янв. 2013 г., 19:19
алгоритм выбирает пару массивов, так что у вас есть comb (k 2) = k * (k-1) / 2. Поскольку каждый массив имеет размер n и объединение принимает O (n), вы получаете O (nk ^ 2)
 mcdowella14 июн. 2012 г., 06:45
Вы можете получить O (n k log k), используя кучу или дерево выбора, чтобы выбрать следующий элемент из k возможных вариантов на каждом этапе. Например. Раздел II Кнута Сортировка и поиск 5.4.1
 Dejell12 мая 2013 г., 15:40
Вы можете использовать очередь, и время будет O (n log k), где n - число целых чисел, а k - количество отсортированных массивов.

Ответы на вопрос(8)

n сравнения для первого массива,2n во-вторых,3n на третий и скоро до(k - 1)n.
Так что теперь сложность становится просто

n + 2n + 3n + 4n + ... + (k - 1)n
= n(1 + 2 + 3 + 4 + ... + (k - 1))
= n((k - 1)*k) / 2
= n(k^2 - k) / 2
= O(nk ^ 2)

:-)

each of size n. It outputs a single sorted array of al,l the elements.

I had thought that this algorithm is O(kn)

Мы можем опровергнуть это противоречием. Определите алгоритм сортировки для m элементов, который использует ваш алгоритм с k = m и n = 1. По условию алгоритм сортировки завершается успешно за O (m). Противоречие, известно, что любой алгоритм сортировки имеет наихудший случай, по меньшей мере, O (m log m).

 19 апр. 2014 г., 18:46
 30 янв. 2015 г., 05:10
На всякий случай, если кто-то здесь споткнется, наихудшее время сортировки nlogn - только для алгоритмов сортировки на основе COMPARISON. Алгоритмы, такие как подсчет или сортировка по группам и т. Д., Не являются сравнительными сортировками и применимы только при соблюдении некоторых ограничений на ввод. Например. Беглый взгляд на счетную сортировку показывает, что если какое-либо значение элемента (скажем, 100) больше размера массива, оно выходит за пределы.
Решение Вопроса

ив обходится k-1 раз, первый как слияние (массив-1, массив-2), второй как слияние (слияние (массив-1, массив-2), массив-3) ... и т. Д. ,

Результатом является слияние k-1 со средним размером n * (k + 1) / 2, что дает сложность O (n * (k ^ 2-1) / 2), которая равна O (nk ^ 2).

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

 11 февр. 2013 г., 06:10
Как вы получили средний размер?
 11 февр. 2013 г., 07:40
Первое слияние имеет размер 2n (два массива размера n). Второй имеет размер 3n (накопленный массив из 2n, а один размером n). Вы должны увидеть, что k-й проход равен (k + 1) n. Средний размер приблизительно равен половине этого значения или n (k + 1) / 2, любой остаточный член не повлияет на анализ O ().

нных массивов {i_1, i_2, i__k}. На каждой итерации алгоритм находит минимальный следующий элемент из всех k массивов и сохраняет его в выходном массиве. Поскольку вы выполняете kn итераций и сканируете k массивов за каждую итерацию, общая сложность составляет O (k ^ 2 * n).

Вот некоторый псевдокод:

Input: A[j] j = 1..k : k sorted arrays each of length n
Output: B : Sorted array of length kn

// Initialize array of indexes
I[j] = 0 for j = 1..k

q = 0

while (q < kn):
    p = argmin({A[j][I[j]]}) j = 1..k           // Get the array for which the next unprocessed element is minimal (ignores arrays for which I[j] > n)
    B[q] = A[p][I[p]]
    I[p] = I[p] + 1
    q = q + 1

1) У вас есть k отсортированных массивов, каждый из которых имеет размер n.

2) Возьмите первый элемент из всех k массивов и создайте последовательность. Затем найдите минимум этой последовательности. Это минимальное значение сохраняется в выходном массиве. Количество сравнений для нахождения минимума из k элементов равно k - 1.

3) Поэтому общее количество сравнений
   = (сравнения / элемент) * количество элементов
   = (k - 1) * k * n
   = k ^ 2 * n // приблизительно

Шаг 1: Объединить массивы (1 и 2), массивы (3 и 4) и т. Д. (k / 2 слияния массива 2n, общая работа kn).

Шаг 2: Массив слияния (1,2 и 3,4), массивы (5,6 и 7,8) и т. Д. (K / 4 слияния из 4n, общая работа kn).

Шаг 3: Повторение...

Будет log (k) таких «шагов», каждый с kn work. Следовательно, общая проделанная работа = O (k.n.log (k)).

Даже в противном случае, если бы мы просто отсортировали все элементы массива, мы все равно могли бы объединить все за O (k.n.log (k.n)) время.

 19 мар. 2014 г., 13:35
Честно говоря, я думаю, что это слияние снизу вверх намного лучше, чем в вопросе OP.

Consider it a matrix of k*n. To add first element to the merged/ final array, you need to compare heads of k arrays. This means for one element in final array you need to do k comparisons.

Так из 1 и 2, для Кn elements, total time taken is O(kк * п).

1 каждый раз. Вы должны просто поддерживать самые последние элементы K в отсортированном наборе.  Вы удаляете самое маленькое и связываете его со следующим элементом. Это должно быть n.log (k)

Соответствующийстатья, Отказ от ответственности: я принимал участие в написании этого

 12 мая 2013 г., 15:44
Правильный. Но вы должны отметить, что вы используете там кучу (например, очередь)
 12 мая 2013 г., 19:12
это то, что я имел в виду под "отсортированным набором" в моем ответе. на самом деле вам нужен отсортированный мультимножество. куча является одной из возможных реализаций.
 16 апр. 2014 г., 19:42
для вашей кучи, вы в конечном итоге будете вставлять элементы nk-1 в вашу структуру. Поскольку вставка стоит O (log (k)), сложность всего слияния должна быть O (nklog (k)), а не nlog (k), как вы сказали. Как указано в вопросе, n - это размер фрагмента. Если мы считаем N общим размером, то имеем N = nk, поэтому сложность в отношении N равна O (Nlog (k))

Ваш ответ на вопрос