Quick Find算法在线连通性操作次数及复杂度符号疑问

实现代码 #

#include <stdio.h>

#define N 10000

main() {
    int i, t, p, q, id[N];

    for (i = 0; i < N; i++) 
        id[i] = i;

    printf("Input pair p q: ");

    while (scanf("%d %d", &p, &q) == 2) {
        if (id[p] == id[q])
            printf("%d %d already connected\n", p,q);
        else {
            for (t = id[p], i = 0; i < N; i++)
                if (id[i] == t)
                    id[i] = id[q];

            printf("pair %d %d not yet connected\n", p, q);
        }

        printf("Input pair p q: ");
    }
}

一、find操作次数计算 #

你给出的6条边分别是：12-6、2-3、0-9、5-4、3-10、10-8。在Quick Find的逻辑中，每处理一对边，都会执行2次find操作——分别读取id[p]和id[q]来判断两点是否连通，不管这对边是否已经连通。

所以总find操作次数为：6 × 2 = 12次。

二、复杂度符号的选择说明 #

1. 针对find操作的次数 #

find操作本身是O(1)的，且每对边固定对应2次find，总次数和边数k严格成正比，这种情况用**Θ(k)**最准确——因为Θ表示紧界，它能精确描述总次数和k的线性关系，既不会高估也不会低估。

2. 针对整个算法的总时间复杂度 #

你给出的所有边都是连接之前不连通的分量，每次union操作都需要遍历整个大小为N的id数组，总时间由k次遍历N的操作主导。这种情况下：

• 用**Θ(kN)**是最精确的，因为每次union都确实执行了N次数组访问，总时间和kN的比例是固定的，满足紧界的定义；
• O(kN)虽然也正确，但它只是上界，无法体现这个特定输入下时间和kN的严格线性对应关系，精度不如Θ(kN)。

如果输入中存在已经连通的边，不需要执行union遍历，那总时间只能用O(kN)描述（因为最坏情况才会达到kN量级），但你的这个输入属于最坏情况的一种，所以Θ(kN)更合适。

内容的提问来源于stack exchange，提问作者Bitwoded S.Demissie