残差网络中路径查找时间复杂度O(V+E')=O(E)的疑问

核心原因可以从两个维度拆解：

• 残差网络的边数规模：原流网络 ( G=(V,E) ) 的残差网络 ( G' ) 中，每条原边 ( (u,v) ) 最多对应两条边（原边和反向边），因此 ( |E'| \leq 2|E| )。大O符号忽略常数系数，所以 ( O(E') = O(E) )。
• 顶点数与边数的关系：流网络分析中默认源点和汇点连通（否则最大流为0，无需路径搜索）。对于连通图，顶点数 ( V \leq E + 1 )，即 ( V = O(E) )。

把这两点结合起来：
( O(V + E') = O(E + E) = O(E) )，因为大O符号会忽略低阶项和常数，所以最终可以简化为 ( O(E) )。

另外在CLRS的算法分析语境里，最大流相关算法通常以边数 ( E ) 作为主导复杂度项，因为实际场景中流网络的边数往往不会比顶点数小一个量级，这种简化是符合工程和理论分析习惯的。

内容的提问来源于stack exchange，提问作者Math.anony