我有一个算法,用于创建通过给定顶点的 P 个顶点上的所有可能子图的列表。这并不完美 但我认为它应该工作正常。问题是当我尝试计算它的时间复杂度时我迷路了。
我想到了类似 T(p) = 2^d + 2^d * (n * T(p-1) )
的东西,其中 d=Δ(G), p=#vertices 需要,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);
}
}
最佳答案
看起来算法有bug,因为在递归调用之后,有可能组合出现的节点也出现在connectedSoFar中,所以检查connectedSoFar.size() + combination.size()等于n似乎是不正确的,因为它可能对一个节点计数两次。
无论如何,否则要分析算法,幂集中有 2d 个元素; “elase”分支中的每个操作都需要 O(n) 时间,因为 connectedSoFar 和组合在一起不能包含超过 n 个节点。然后将元素添加到 connectedSoFar 需要 O(n log n) 时间,因为 |combination| ≤ n。组合节点上的迭代发生 O(n) 次;其中有O(d)的操作构造hash集合k然后递归调用。
然后用 X(n) 表示过程的复杂性,其中 n 是参数。你有
X(n) ~ 2d (n + n log n + n (d + X(n - 1)))
因为在递归调用中您至少向图中添加了一个顶点,所以在实践中递归调用中的参数 n 实际上至少减少了一个。
简化为
X(n) ~ 2d (n (1 + d + log n + X(n - 1)))
因为d是常数,记D = 2d,消去常数1,得到
X(n) ~ D n (d + log n + X(n - 1))
你可以分析为
X(n) ~ (2d)n n! (d + log n)
证明你的算法真的很浪费时间:)
关于java - n-顶点子图枚举的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6167507/