Bron-Kerbosch 算法时间复杂度分析：递归深度为何为 n？

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

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

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