时间戳

首页 > 解决方案 > 获取 N 叉树中较大祖先的数量

python - 获取 N 叉树中较大祖先的数量

问题描述

我们有一棵树，其节点编号从1到N。vals它以 3 个数组, edge1,的格式提供给我们edge2。vals[i] 的值为 node i + 1。从 edge1[i] 到 edge2[i] 有一条边。树的根为 1。

我想为树中的每个节点计算大于当前节点值的祖先的数量，并将它们返回到一个数组中。

这是一个有效的算法：

def get_larger_ancestors(vals, edge1, edge2):
    tree = defaultdict(set)
    for u, v in zip(B, C):
        tree[u].add(v)
        tree[v].add(u)

    parents = {1:None}
    que = deque([1])
    seen = set()
    while que:
        current = que.popleft()
        seen.add(current)
        for node in tree[current]:
            if node not in seen:
                parents[node] = current
                que.append(node)

    result = [None] * len(A)
    for val in tree:
        count = 0
        target = A[val - 1]
        p = val
        while p:
            p = parents[p]
            if p is None: break
            if A[p - 1] > target:
                count += 1
        result[val - 1] = count


    return result

上述算法的时间复杂度在最坏情况下是二次的。它必须在大约 10^6 个节点上运行。

如何提高时间复杂度？

标签： pythonalgorithmtree

解决方案

对于您的算法的某些图的复杂性，例如来自节点的O(n)树有根节点的直接子节点。对于某些图，它是，例如，有一条长腿的树。然后就是。mm-1O(n^2)1+2+3+..+(n-1)

您可以做的不是遍历所有父母，而是将它们存储在平衡树中，并以对数时间而不是当前线性时间查找每个下一个孩子的位置。通过此更改，您的最坏时间将从二次减少到O(n*log(n))。有关对数求和公式，请参见此处。

推荐阅读