如何求这段js代码的时间和空间复杂度？

Question

这是我的平台用来查找两个节点之间关系的两个代码。 代码1：

const getNodeRelationship = (node1, node2) => {
    // if node1 and node2 are the same node
    if (node1 === node2) return null;

    // check direct parent
    let parent = node1.parentElement
    if (parent === node2) {
        return 'parent';
    }

    // if both node1 and node2 have the same parent
    if (node1.parentNode === node2.parentNode) {
        return 'sibling';
    }

    // check direct children
    for (const child of node1.children) {
        if (child === node2) return 'child';
    }

    return null;
}

代码2：

const getNodeRelationship = (node1, node2) => {
    // Helper function to check the relation between the two nodes
    const checkParentDirectChild = (parent, child) => {
        // If the parent node exists, iterate over its childNodes
        if (parent) {
            for (const curNode of parent.childNodes) {
                if (curNode === child) {
                    return true;
                }
            }
        }
        return false;
    }

    // if node1 and node2 are the same node
    if (node1 === node2) {
        return null;
    }
    
    // if node2 is a direct child of node1
    if (checkParentDirectChild(node1, node2)) {
        return 'child';
    }

    // if node1 is a direct child of node2
    if (checkParentDirectChild(node2, node1)) {
        return 'parent';
    }
    
    // if both node1 and node2 have the same parent
    if (checkParentDirectChild(node1.parentNode, node2) && checkParentDirectChild(node2.parentNode, node1)) {
        return 'sibling';
    }
    
    return null;
}

我认为当我们检查两个节点之间的直接父子关系时，这两个代码的 tc 和 sc 都是 O(1)。因为我们没有做任何类型的 DFS 或 BFS

但是如果node1有100万个子节点，而node2是最后一个，那么在提出的两个解决方案中，for不会运行一百万次吗？

我很困惑。谁能帮我验证一下时间和空间吗？

Answer 1

但是如果node1有100万个子节点，而node2是最后一个，那么在提出的两个解决方案中，for不会运行一百万次吗？

是的，在最坏的情况下会的。这就是为什么您需要知道树的分支因子𝑏是什么的原因。平均或最大分支因子都可以。由于对任一节点的子节点进行循环，时间复杂度为 O(𝑏)。

空间复杂度为O(1)。