Поддерево максимального соответствия: различия между версиями

В результате число интересных пар (u, v) сокращается до O(n log n). Обработка одной пары требует O(1) времени (это менее очевидно, поскольку определение потомков вершины u, являющихся корнями поддеревьев, с которыми могут быть сопоставлены два поддерева v, является нетривиальной задачей). Построение вышеописанного порожденного поддерева может быть выполнено за время O(jL1j), что будет показано далее. Это достигается путем предварительной подготовки деревьев T1 и T2 за время O(n) таким образом, чтобы нахождение наименьшего общего предка занимало O(1) времени.

Оптимизация 2: как и в [ ], когда деревья не являются полными бинарными деревьями, алгоритм рассматривает центроидные пути и сопоставляет пары центроидных путей. Стоимость O(log n), которую алгоритм из [4] вносит в обработку каждой такой интересной пары, возникает в случае крупных (полиномиальных относительно n) экземпляров обобщенной задачи нахождения самой длинной возрастающей последовательности. На первый взгляд представляется неочевидным, что крупные экземпляры этой задачи могут возникать для достаточно большого числа интересных пар; к сожалению, на деле это оказывается именно так. Однако эти экземпляры задачи могут иметь определенную структуру. Используя (статические) взвешенные деревья, можно обрабатывать пары интересных вершин за время O(1) в среднем на одну пару с использованием подходящим образом параметризованного анализа.

Эту технику можно обобщить на случаи более высоких степеней d > 2, за счет сочетания ее с техниками из ([6, глава 2]) для неограниченных степеней. Полученный алгоритм теоретически должен выполняться за время O(minfnpd log2 n; nd log n logdg); однако на деле время его исполнения составляет O(npd log n).