如何分析两段JS节点关系判断代码的时间与空间复杂度？

我原本认为以下两段判断DOM节点直接关系的JavaScript代码，时间复杂度（TC）和空间复杂度（SC）均为O(1)——毕竟只检查直接父子/兄弟关系，没用到DFS或BFS。但如果node1有百万个子节点且node2是最后一个，循环会执行百万次，这让我产生了困惑，想验证两段代码的复杂度。

Code 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;
}

Code 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;
}

时间复杂度分析 #

Code 1

• 前三个判断逻辑都是O(1)：节点全等判断、parentElement/parentNode的属性访问与比较，都是直接的内存操作，不涉及遍历。
• 最后的子节点遍历循环：最坏情况下，需要遍历node1的所有直接元素子节点（children只包含元素节点）才能确定结果，设子节点数量为n，这部分时间复杂度是O(n)。
• 综上，Code 1的时间复杂度为O(n)，n是node1的直接元素子节点数量（最坏场景）。

Code 2

• 辅助函数checkParentDirectChild的核心是遍历父节点的childNodes（包含元素节点、文本节点、注释等所有子节点），设该父节点的子节点总数为m，函数的时间复杂度为O(m)。
• 最坏场景下，代码会依次执行所有判断：先遍历node1的childNodes（O(m1)，m1为node1的子节点总数），再遍历node2的childNodes（O(m2)，m2为node2的子节点总数），最后遍历共同父节点的childNodes两次（O(m_p)，m_p为共同父节点的子节点总数）。
• 综上，Code 2的时间复杂度为O(max(m1, m2, m_p))，其中m1、m2、m_p分别对应node1、node2、共同父节点的子节点总数。

空间复杂度分析 #

两段代码都只使用了固定数量的局部变量（比如parent、循环变量、辅助函数的参数等），没有动态分配随输入规模增长的内存（比如数组扩容、递归调用栈）。无论节点有多少子节点，占用的内存空间都是恒定的，因此两段代码的空间复杂度均为O(1)。

困惑解答 #

你之前误以为是O(1)，是忽略了“输入规模”包含节点的子节点数量这一点。O(1)要求时间不随任何输入规模变化，但这里的循环次数会随目标节点的子节点数量线性增长，因此时间复杂度不是常数级，而是线性级。

内容的提问来源于stack exchange，提问作者Jatin