Какова сложность во время выполнения алгоритма рекурсивного дерева, квадратичного по количеству различных размеров дочерних поддеревьев?

Question

У меня есть алгоритм, который работает с корневым деревом.Сначала он рекурсивно вычисляет результаты для каждого дочернего поддерева корня.Затем он делает некоторую работу, чтобы объединить их.Объем работы с корнем - K ^ 2, где K - число различных значений среди размеров поддеревьев.

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

Answer 1

Это регулируется основной теоремой алгоритмов деления и согласования. Для этого конкретного случая (я читал между строк в том, что вы описали) это в основном определяется тем, сколько работы требуется на одном узле, чтобы объединить работу, скомпилированную для значений K в поддеревьях. В частности, если она меньше K работы, тогда в стоимости преобладают затраты на самом низком уровне, и в сумме она будет O(K), если работа на данном уровне составляет O(K), тогда общая работа становится O(K log(K)). Для работы на уровне выше O(K) преобладает работа на высшем уровне. Для этого у нас есть алгоритм сложности выполнения O(K^2).

.