循环中递归函数的时间复杂度是多少？手动计算步数显示 2^n 但为什么？

Question

所以我遇到了一个问题，即从给定的点集构造每个可能的共线点集。我设法为这个问题编写了一个回溯算法。但是，我无法真正从数学上显示时间复杂度。我得到了 O(n!)，但它似乎不正确，它运行示例输入的速度太快了。我手动计算，结果为 O(2^n) 。为什么是这个数字呢？我没有 2 个递归调用，并且我的递归调用位于循环内。我应该如何用数学方式显示这个结果？

我这里有整个算法，有问题的函数是backtracking_recursive

# Check if three points are collinear
def check_if_collinear(point_A:tuple, point_B:tuple, point_C:tuple):
    determinant = float(point_A[0] * (point_B[1] - point_C[1])+
                        point_B[0] * (point_C[1] - point_A[1])+
                        point_C[0] * (point_A[1] - point_B[1]))
    triangle_area = 0.5 * determinant
    return triangle_area == 0


# recursive backtracking to find sets of collinear points
# starts in the points list from index start, adds an element to current_set
# checks if lastly added element is collinear with first element and current point at index i
def backtracking_recursive(start:int, current_set:list, collinear_sets:list, points:list):
    global counter
    if len(current_set) > 2:
        collinear_sets.append(current_set.copy())

    for i in range(start, len(points)):
        if not current_set or check_if_collinear(current_set[0], current_set[-1], points[i]):
            current_set.append(points[i])
            backtracking_recursive(i + 1, current_set, collinear_sets, points)
            current_set.pop()

# helper function for solution
def find_collinear_sets(points:list):
    collinear_sets = []
    backtracking_recursive(0, [], collinear_sets, points)
    return collinear_sets

谢谢您的帮助！

Answer 1

在最坏的情况下（所有点共线），您构建整个幂集，即所有 2^n 子集。

你会得到所有n！ 排列如果你递归了除了第i个元素之外的所有元素，但你没有。您只能对第 i 个之后的元素进行递归。

但是，时间复杂度仍然不是 O(2^n) 而是 O(n•2^n)，因为您复制非平凡子集且它们的平均长度为 ~n/2。