Рекуррентное отношение и временная сложность поиска следующего большего размера в общем дереве

Вопрос: Даны общее дерево и целое число 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
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
0
105
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Во-первых: пожалуйста, используйте разные символы для 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 затрудняет применение основной теоремы.

Отличный и понятный анализ. Спасибо.

Mod 11.12.2020 14:37

Другие вопросы по теме