algorithm - 估计图形算法的时间复杂度

Question

我有一个由邻接矩阵表示的无向图 G = (V, E)。对于每条边，我必须计算它的弱点。弱点d计算如下:

其中 Nx 是 x 的直接节点集(直接节点是指从 x 开始的路径为 1 的节点)。
我已经写了这个算法，但我不确定如何评估它的复杂性。

float **graph_weakness(struct graph *g)
{
    int i;
    int j;
    int n = g->n;
    struct edge *edge;
    int rel_union;
    int rel_intersect;
    int idx;
    float **m = graph_to_matrix(g);

    /* complessità: O(|V|/2|E|) */
    for (i = 0; i < n; i++) {
        edge = g->nodes[i]->edges;
        while (edge != NULL) {
            idx = edge->idx;
            if (m[i][idx] == MATRIX_SET) {
                rel_union = 0;
                rel_intersect = 0;
                for (j = 0; j < n; j++) {
                    if (m[i][j] != 0.0 || m[idx][j] != 0.0) {
                        rel_union++;
                    }
                    if (m[i][j] != 0.0 && m[idx][j] != 0.0) {
                        rel_intersect++;
                    }
                }
                m[i][idx] = 1 - (float) rel_intersect / rel_union;
                m[idx][i] = m[i][idx];
            }
            edge = edge->next;
        }
    }

    return m;
}

该算法在边上迭代，并使用从 1..|V|. 开始的循环为每条边计算集合的交集和并集
Tha 矩阵是对称的，因此计算是在一半的边上进行的。
因此，复杂度应该是 O(|E|/2 * |V|) = O(|E|*|V|)，对吗？

Answer 1

线

float **m = graph_to_matrix(g);

可能是Θ(|V| |E|)

(这取决于你的矩阵库)。

---

(可能与您问题中的陈述有些相反)，该算法从遍历所有节点开始

for (i = 0; i < n; i++) {

对于每个节点，它遍历所有邻居

while (edge != NULL) {

对于每个邻居，它再次遍历所有节点

for (j = 0; j < n; j++) {

因此，假设您的图具有邻接表表示，这第一个 + 第二个循环总共运行 O(|E| + |v|) 次，并且每次迭代遍历 | V| 项。

---

因此，该算法是 O((|E| + |V|) |V|)。