Блог

Вопрос: Дано общее дерево и целое число n. Найдите и верните узел со следующим большим элементом в дереве, т.е. Найдите узел со значением чуть больше n.

Хотя я смог решить это O (n), удалив более поздний цикл for и выполнив сравнения при вызове рекурсии. Мне немного любопытно узнать о временной сложности следующей версии кода.

Я пришел к рекуррентному соотношению в виде T (n) = T (n-1) (n-1) = O (n ^ 2). Где T(n-1) — время, затраченное дочерними элементами, и (n-1) для нахождения следующего большего (второго цикла for). Я все сделал правильно? или я что-то упускаю?

 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 это затрудняет применение основной теоремы.