泛型树中寻找下一个大树的递归关系和时间复杂度

Question

问题：给定一棵泛型树和一个整数n。查找并 return 树中具有下一个较大元素的节点，即查找值刚好大于 n 的节点。

虽然我能够通过删除后面的 for 循环并在调用递归时进行比较来解决它是 O(n)。我对以下代码版本的时间复杂度有点好奇。

我想出了递归关系 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

Answer 1

首先：O-Notation和输入值请使用不同的字符。

您恰好“触摸”了每个节点一次，因此结果应该是 O(n)。有点特别的是你的算法之后找到最小值。您可以将其包含在 go-though-all-children 循环中，以便更轻松地进行重复估计。实际上，您还对列表的最小值进行了递归估计。

您的递归方程应该看起来更像 T(n) = a*T(n/a) + c = O(n)，因为在每个步骤中您都有 a children 形成 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 使得应用主定理变得更加困难。

泛型树中寻找下一个大树的递归关系和时间复杂度

Recurrence relation and time complexity of finding next larger in Generic tree

python

algorithm

recurrence