3

我有一个算法，用于通过给定顶点创建 P 顶点上所有可能的子图的列表。它并不完美，但我认为它应该可以正常工作。问题是当我尝试计算它的时间复杂度时我迷路了。

我想出了类似的东西T(p) = 2^d + 2^d * (n * T(p-1) )，在哪里d=Δ(G), p=#vertices required, n=|V|。这真的只是一个猜测。谁能帮我这个？

使用的 powerSet() 算法应该是O(2^d)or O(d*2^d)。

private void connectedGraphsOnNVertices(int n, Set<Node> connectedSoFar, Set<Node> neighbours, List<Set<Node>> graphList) {
    if (n==1) return;

    for (Set<Node> combination : powerSet(neighbours)) {
        if (connectedSoFar.size() + combination.size() > n || combination.size() == 0) {
            continue;
        } else if (connectedSoFar.size() + combination.size() == n) {
            Set<Node> newGraph = new HashSet<Node>();
            newGraph.addAll(connectedSoFar);
            newGraph.addAll(combination);
            graphList.add(newGraph);
            continue;
        }

        connectedSoFar.addAll(combination);
        for (Node node: combination) {
            Set<Node> k = new HashSet<Node>(node.getNeighbours());
            connectedGraphsOnNVertices(n, connectedSoFar, k, graphList);
        }
        connectedSoFar.removeAll(combination);
    }
}
4

1 回答 1

1

看起来该算法有一个错误，因为在递归调用之后，组合出现的节点也可能出现在 connectedSoFar 中，因此检查 connectedSoFar.size() + combination.size() 是否等于 n 似乎不正确，因为它可能会计算一个节点两次。

无论如何，否则要分析算法，您在 powerset 中有 2 d个元素；“elase”分支中的每个操作都需要 O(n) 时间，因为 connectedSoFar 和组合在一起不能包含超过 n 个节点。然后将元素添加到 connectedSoFar 需要 O(n log n) 时间，因为 |combination| ≤ n。组合节点上的迭代发生 O(n) 次；在其中有 O(d) 操作来构造散列集 k 然后递归调用。

然后用 X(n) 表示过程的复杂性，其中 n 是参数。你有

X(n) ~ 2 d (n + n log n + n (d + X(n - 1)))

因为在递归调用中，您已经向图中添加了至少一个顶点，所以实际上递归调用中的参数 n 实际上至少减少了一个。

将其简化为

X(n) ~ 2 d (n (1 + d + log n + X(n - 1)))

因为 d 是常数，标记 D = 2 d，消除常数 1，你得到

X(n) ~ D n (d + log n + X(n - 1))

你可以分析为

X(n) ~ (2 d ) n n! (d + log n)

表明你的算法真的很浪费时间:)

于 2011-05-29T20:37:42.180 回答