Вопрос: Даны общее дерево и целое число n. Найдите и верните узел со следующим большим элементом в дереве, т.е. найдите узел со значением чуть больше n.
Хотя я смог решить, что это O (n), удалив более поздний цикл for и выполнив сравнения при вызове рекурсии. Мне немного любопытна временная сложность следующей версии кода.
Я придумал рекуррентное соотношение как T (n) = T (n-1) + (n-1) = O (n ^ 2). Где T(n-1) для времени, затраченного детьми, и + (n-1) для нахождения следующего большего (секунда для цикла). Я сделал это правильно? или я что-то упускаю?
def nextLargestHelper(root, n):
"""
root => reference to root node
n => integer
Returns node and value of node which is just larger not first larger than n.
"""
# Special case
if root is None:
return None, None
# list to store all values > n
largers = list()
# Induction step
if root.data > n:
largers.append([root, root.data])
# Induction step and Base case; if no children do not call recursion
for child in root.children:
# Induction hypothesis; my function returns me node and value just larger than 'n'
node, value = nextLargestHelper(child, n)
# If larger found in subtree
if node:
largers.append([node, value])
# Initialize node to none, and value as +infinity
node = None
value = sys.maxsize
# travers through all larger values and return the smallest value greater than n
for item in largers: # structure if item is [Node, value]
# this is why value is initialized to +infinity; so as it is true for first time
if item[1] < value:
node = item[0]
value = item[1]
return node, value
Во-первых: пожалуйста, используйте разные символы для O-нотации и входных значений.
Вы «касаетесь» каждого узла ровно один раз, поэтому результат должен быть O(n)
. Немного особенным является ваш алгоритм, который впоследствии находит минимум. Вы можете включить это в свой цикл «пройти все дочерние элементы» для упрощения оценки повторения. Как бы то ни было, вы также должны выполнить оценку повторения для минимума списка.
Ваше рекуррентное уравнение должно больше походить на T(n) = a*T(n/a) + c = O(n)
, так как на каждом шаге у вас есть a
дочерние элементы, формирующие a
поддеревья размером (n-1)/a
. На каждом шаге у вас есть рядом с некоторыми постоянными факторами также вычисление минимума списка с не более чем a
элементами. Вы можете написать это как a*T(n/a) + a*c1 +c2
, что то же самое, что и a*T(n/a) + c
. Фактическая формула будет выглядеть примерно так: T(n) = a*T((n-1)/a) + c
, но n-1
затрудняет применение основной теоремы.
Отличный и понятный анализ. Спасибо.