求助：基于伪随机函数的图边添加循环时间复杂度分析

这段代码先构建一个基于随机路径的邻接表图，再额外添加 m-n+1 条随机边。核心难点是分析最后一段添加边的循环的时间复杂度，以下从期望时间复杂度角度，结合图的稀疏/稠密性展开分析：

目标代码段 #

int mrim = m-n+1;
    
for (int k=0;k<mrim;k++){
    int i = rnd.nextInt(0,n);
    ArrayList<Integer> a = adjlist.get(i);
        
    while(a.size()==n-1){
        i = rnd.nextInt(0,n);
        a = adjlist.get(i);
    }

    int j = rnd.nextInt(0,n);
        
    while (i==j || a.contains(j)){
        j = rnd.nextInt(0,n);
    }
    adjlist.get(i).add(j);
    adjlist.get(j).add(i);
}

核心步骤拆解 #

每次循环要完成两个关键随机抽样：

1. 找到一个非全连接的节点 i（即 i 的邻接表长度不等于 n-1，还能添加新边）
2. 找到一个与 i 不重复、且未与 i 相连的节点 j

我们用几何分布的期望性质（成功概率为 p 时，期望尝试次数为 1/p）分析每个步骤的期望耗时。

情况1：稀疏图（m = O(n)） #

此时总边数 m 与节点数 n 同阶，额外添加的边数 mrim = m-n+1 = O(n)，每个节点的平均度数为常数（O(1)）：

• 第一个 while 循环：不存在全连接节点，每次随机选 i 都符合要求，期望尝试次数为1，耗时可忽略。
• 第二个 while 循环：节点 i 的邻接表长度为 O(1)，可用的 j 数量约为 n，选到符合条件的 j 的概率接近1，期望尝试次数为1；a.contains(j) 是线性扫描邻接表，耗时 O(1)。
• 每条边的期望耗时为 O(1)，总循环的期望时间复杂度为 O(mrim) = O(n)。

情况2：稠密图（m = Θ(n²)） #

此时总边数接近完全图的边数，额外添加的边数 mrim = Θ(n²)，节点平均度数为 Θ(n)：

• 第一个 while 循环：随着边的添加，全连接节点数逐渐增加，但只有当图接近完全图时，这个循环的尝试次数才会上升；而此时剩余需要添加的边数已经很少，对总耗时的影响可忽略。
• 第二个 while 循环：利用期望线性性计算总耗时：所有尝试中，检查 j 是否存在的总次数对应的耗时，等于每个节点邻接表长度的总和乘以期望尝试次数，邻接表总长度为 2m = Θ(n²)，总期望尝试次数为 Θ(n²)，两者相乘后总耗时仍为 Θ(n²)。
• 总循环的期望时间复杂度为 O(mrim) = O(n²)。

总结 #

• 稀疏图场景：期望时间复杂度为 O(n)
• 稠密图场景：期望时间复杂度为 O(n²)
• 通用结论：该循环的期望时间复杂度为 O(m)，因为 m 在稀疏图中是 O(n)，稠密图中是 Θ(n²)，与上述分析一致。

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