Если у вас есть k разных деревьев, то вам нужно выполнить всего (k - 1) слияний, чтобы собрать их в одно дерево.Поэтому вопрос в том, сколько времени займет каждое слияние.
Предположим, что вы принимаете стратегию, согласно которой вы всегда объединяете два наименьших дерева вместе в любой момент времени.Если у вас есть m деревьев, доступных для этого, то размер второго по величине дерева будет доминировать во время выполнения слияния.Этот размер составляет самое большее (n - 1) / (k - 1), что происходит, когда наименьшее дерево имеет только один элемент, а все остальные деревья имеют все элементы в них.Это означает, что если вы сделаете k слияний, стоимость будет
N - 1 N - 1 N - 1 N - 1
----- + ----- + ----- + ... + -----
K - 1 K - 2 K - 3 1
Но это (n - 1) H (k - 1), где H (k-1) - (k-1) ст номер гармоники .Тогда все это выражение равно O (n log k), поэтому общая работа, выполненная во время слияния, составляет O (n log k).
Тем не менее, в дополнение к этому у вас должен быть простой способ найти двасамые маленькие деревья в каждой точке.Это может быть сделано с приоритетной очередью, которая хранит деревья в порядке убывания размера.У вас будет k - 1 раунд выполнения двух очередей из дерева с последующей одной постановкой в очередь, поэтому общее время для всех приоритетных операций очереди составляет O (k log k).Это также O (n log k), поэтому общее время выполнения алгоритма составляет O (n log k).
Я почти уверен, что вы не можете добиться гораздо большего, чем это, потому что вы могли быначать с каждого из n узлов в своем собственном дереве AVL (k = n).Если бы вы могли объединиться быстрее, чем Ω (n log n), то вы могли бы сортировать быстрее, чем Ω (n log n), используя только сравнения, построив дерево AVL, образованное путем объединения всех меньших деревьев, а затем выполнив обход по порядку в O (n) время для сортировки лучше, чем Ω (n log n), что , как известно, невозможно .
Надеюсь, это поможет!