Какова связь между слияниями и количеством элементов в слиянии k-way - PullRequest
0 голосов
/ 18 марта 2009

Вопрос в том, как при слиянии k-way сколько операций слияния мы выполним Например: двухстороннее объединение: 2 узла 1 объединение; 3 узла 2 сливаются; 4 узла 3 сливаются. Таким образом, мы получаем M (n) = n-1.

Что за M (n), когда k произвольно?

Ответы [ 3 ]

1 голос
/ 19 марта 2009

ОК, чтобы ответить на оригинальный вопрос, как указано:

Для объединения k блоков с использованием последовательности двусторонних слияний всегда требуется ровно k - 1 слияние, поскольку независимо от выбранной пары блоков вы выбираете объединение в любой момент времени, объединение их уменьшает общее количество блоков на 1.

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

1 голос
/ 18 марта 2009

2-сторонние слияния наиболее эффективны при объединении блоков одинакового размера, поэтому наиболее эффективным слияниями k на основе 2-сторонних слияний является первое слияние блока 1 с блоком 2, блока 3 с блок 4 и т. д., затем объедините первые два результирующих блока и т. д. Это в основном то, как работает слияние, и приводит к времени O ( kn log k ), предполагая, что каждый из блоков k содержит n Предметы. Но он эффективен только в том случае, если все блоки имеют ровно n элементов, а k - это степень 2, поэтому ...

Вместо выполнения k отдельных проходов слияния вы можете использовать один проход, в котором используется куча, содержащая первый элемент каждого блока (т.е. всего k элементов):

  1. Чтение самого низкого элемента из кучи (время O (log k ))
  2. Запиши это
  3. вытащи его из кучи
  4. Если блок, из которого пришел этот предмет, еще не исчерпан, поместите следующий предмет из него в кучу (снова O (log k )).
  5. Повторяйте, пока куча не опустеет.

Если имеется всего kn элементов, это всегда занимает время O ( kn log k ) независимо от того, как они распределены среди блоков, и независимо от того, является ли k степенью 2. Ваша куча должна содержать (item, block_index) пар, чтобы вы могли определить, из какого блока происходит каждый элемент.

0 голосов
/ 19 марта 2009

да, способ кучи может быть более эффективным. Но каков ответ на оригинальный вопрос? Я обнаружил, что ответа на этот вопрос может не быть, поскольку это, возможно, не полное дерево k-way, поэтому 4-way может вернуться к 3-way, 2-way.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...