n个顶点子图枚举的时间复杂度

Question

我有一个算法，可以通过给定的顶点创建包含所有可能子图的列表。虽然不完美，但我认为它应该能正常工作。问题是当我尝试计算其时间复杂度时会迷失方向。

我想到了类似于 T(p) = 2^d + 2^d * (n * T(p-1)) 的东西，其中 d=Δ(G)，p=#vertices required，n=|V| 。这只是一种猜测。有人能帮我吗？

使用的 powerSet() 算法应该是 O(2^d) 或 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);
    }
}

- Nejc Saje

Answer 1

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

无论如何，要分析算法，您在幂集中有2^d个元素；“elase”分支中的每个操作都需要O(n)时间，因为connectedSoFar和combination一起不能包含超过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! (d + log n)

这表明你的算法确实是一个时间浪费 :)

- Antti Huima

---

非常感谢这个深入的分析！看起来确实很费时间，幸运的是我不需要它非常高效 - 但也许这里有人可以指点我更好的方法。再次感谢。 - Nejc Saje