Программа рекурсивного выполнения восстановления дерева

Я пытаюсь выяснить время выполнения рекурсивного алгоритма, который я придумал. Алгоритм, с учетом обхода дерева по предзаказу и inOrder, находит обход по PostOrder. Вот мой алгоритм:

Recovery(preOrder, inOrder):
root = preOrder[0]
rootIndex = inOrder.find(root)

if preOrder.length <= 0
return;

leftPreord = preOrder[1...rootIndex]
leftInord = inOrder[0...rootIndex]
rightPreord = preOrder[rootIndex + 1 ... End]
rightInord = inOrder[rootIndex + 1 ... End]

Recovery(leftPreord, leftInord)
Recovery(rightPreord, rightInord)

print preOrder[0]

У меня вопрос, если этот алгоритм в основном имеет то же время выполнения, что и алгоритм MergeSort, O (nlogn).

Нерекурсивная часть алгоритма (в основном оператор .find ()) выполняется за время O (n), затем два рекурсивных вызова выполняются за время T (n / 2). Следовательно, T (n) = T (n / 2) + O (n). Высота дерева равна log n, и каждый уровень выполняется за n раз, следовательно, O (nlogn). Меня беспокоит только то, что для каждого рекурсивного вызова это технически T ((n-1) / 2), потому что мы оставляем текущий корень позади. Это имеет значение?

0

Решение

Твоя логика здорова. Шаги каждой итерации состоят из суммы операций O (1) и O (n). Их сумма просто является высшим порядком любого из шагов: O (n). У вас есть уровни log (n) [base2], что действительно оставляет вам алгоритм O (n log n).

Хорошие рассуждения.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector