Bron-Kerbosch算法的时间复杂度如何求得具体展开为什么递归深度为n

Bron-Kerbosch算法的时间复杂度可以通过递归树的分析得到。递归树的每一层代表了算法中一个过程的执行。每个过程都是从一个未覆盖点集中选择一个点，添加到一个候选点集中，并从该点集中选择一个点与它相邻的点，添加到一个已覆盖点集中。

假设有n个点，m条边，每个点的度数不超过d。在最坏情况下，算法会递归n次，每次都需要枚举未覆盖点集和候选点集中的点，以及它们相邻的点。因此，每次递归的时间复杂度为O(n*d^2)。

递归深度为n的原因是，每次递归都会选择一个未覆盖点集中的点，直到所有点都被覆盖。因此，递归深度最多为n。在最坏情况下，每个点都与其他所有点相邻，因此每次递归时候选点集中都有n-1个点，未覆盖点集中有0个点，导致递归深度为n。