求共线点集的循环内递归回溯算法时间复杂度为何是O(2^n)？

我需要从给定点集中构造所有可能的共线点集，已经实现了回溯递归算法，但无法从数学上推导其时间复杂度。最初认为是O(n!)，但示例输入的运行速度远超预期，手动计数后推测时间复杂度为O(2^{n)。不过我有个疑问：算法中没有两个显式的递归调用，且递归位于循环内部，为何时间复杂度是O(2}n)？希望能从数学上证明这一结论。

以下是完整算法代码，核心疑问函数为backtracking_recursive：

# 检查三点是否共线
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


# 递归回溯寻找共线点集
# 从points列表的start索引开始，将元素加入current_set
# 检查新加入的点是否与集合首尾两点共线
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()

# 解决方案辅助函数
def find_collinear_sets(points:list):
    collinear_sets = []
    backtracking_recursive(0, [], collinear_sets, points)
    return collinear_sets

时间复杂度推导 #

核心逻辑梳理 #

算法的核心是按索引顺序遍历点集，每次仅选择与当前集合共线的点加入，然后递归处理后续索引的点（回溯时弹出已选点）。最坏情况为所有点共线，此时每个点都会满足加入条件，递归调用的规模达到最大。

递推关系式推导 #

定义T(k)为处理k个连续点（从某个start索引开始，剩余k个点）时的总递归调用次数（包含所有子调用）：

1. 当k=0（无剩余点）：T(0)=1，对应一次空调用（直接返回）。
2. 当k≥1：
   当前调用会遍历这k个点，每个点都会触发一次递归（因为所有点共线，条件满足）。对于第m个点（从0计数），递归处理剩余的k - m - 1个点，对应调用T(k - m - 1)。

因此递推式为：

T(k) = 1 + T(k-1) + T(k-2) + ... + T(0)

其中1代表当前调用本身，后续项是每个点触发的子调用次数之和。

化简递推式 #

观察到：

T(k-1) = 1 + T(k-2) + ... + T(0)

将其代入T(k)的表达式：

T(k) = T(k-1) + T(k-1) = 2*T(k-1)

结合初始条件T(0)=1，可递推得出：

T(k) = 2^k

结论 #

当所有点共线（最坏情况），算法的时间复杂度为O(2^n)，其中n是点集的大小。

对疑问的解释 #

虽然算法没有显式的两个递归分支，但当所有点共线时，每个点都对应两种选择：

• 跳过该点：继续循环处理下一个点；
• 选择该点：触发递归处理后续点，回溯后回到循环。

这种结构等价于二叉树的递归展开（每个节点对应两个子分支），最终时间复杂度呈现指数级增长，而非阶乘级（阶乘级对应全排列式的递归选择，与本算法的顺序子集选择逻辑不同）。

内容的提问来源于stack exchange，提问作者Újfalusi Ábel