为何我认为LeetCode133.克隆图的时间复杂度是O(E)而非O(V+E)

问题描述 #

针对LeetCode图论题目133.克隆图的DFS解法，我在时间复杂度计算上存在疑问，以下是我提交的JavaScript实现代码：

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if(!node) return null;
    const visited = new Map();
    
    const dfs = (node) => {
        const n = [];
        if(visited.has(node.val)) return visited.get(node.val);
        let newNode = new Node(node.val);
        visited.set(node.val,newNode);
        
        for(let on of node.neighbors){
            n.push(dfs(on));
        }
        
        newNode.neighbors = n;
        return newNode;
    }
    
    return dfs(node);
};

我的解法遍历逻辑可参考对应DFS遍历示意图。

设V、E分别为图的顶点数、边数，我看到很多资料称该解法的时间复杂度为O(V+E)，但我并不认同，我认为该场景下时间复杂度应为O(E)，核心理由如下：

• 本题输入仅为单个节点对象而非邻接表结构
• 目标图为无向连通图，仅需从输入节点出发做深度遍历即可覆盖整张图，不需要为每个节点遍历连续存储的邻接序列，逻辑和树类问题的普通DFS完全一致

我想确认自己的理解是否存在错误，如果有误，对应的认知误区在哪里？

解答 #

你的理解存在错误，核心误区是混淆了边遍历的开销和节点操作的固有开销，同时对图遍历时间复杂度的统计逻辑存在偏差，具体说明如下：

• 首先明确连通无向图的基本性质：包含V个顶点的连通无向图，边数E的取值范围是V-1 ≤ E ≤ V(V-1)/2，不存在E远小于V的情况。哪怕是边数最少的树结构，也满足E=V-1，此时O(V+E)和O(E)属于同量级，但时间复杂度的标准表述需要覆盖所有边界场景，不能因为部分场景下量级等价就省略其中一项。
• 你的代码中存在和边遍历完全无关、每个节点必执行的固定开销：每访问到一个未遍历的节点，你都会执行创建新节点、向visited哈希表写入键值对的操作，这部分操作总共有V次，和边数没有直接关联。举个极端边界例子：如果图只有1个孤立节点，没有任何边（V=1，E=0），你的代码依然会完成判空、创建节点、写入哈希表、返回结果的全流程，总操作数是常数级，如果按O(E)计算会得到0复杂度的结论，显然和实际执行情况矛盾。
• 你提到的「输入是单个节点而非邻接表，不需要遍历连续邻接序列」这个点不影响复杂度统计：不管邻接关系用什么结构存储，你遍历每个节点邻居列表的总次数，本质是把所有无向边遍历了2次（每条边连接两个节点，会在两个节点的邻居列表中各出现一次），这部分开销确实是O(E)，但不能因此忽略访问每个节点本身产生的O(V)开销。
• 树的DFS时间复杂度标准表述同样是O(节点数+边数)，只是因为树的边数恒等于节点数-1，两者为同量级，很多资料会简写为O(n)（n为节点数），本质和图遍历O(V+E)的计算逻辑没有区别。

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