查找该算法的时间复杂度

Question

我试图找到这个算法的时间复杂度，我尝试使用 T(n) 计算它，假设 T(n) = 2T(n-1) + Const 结果得到 O(n)。

bool sum(int arr[], int x, int n, int index){
    if(x == 0 && index == 3)
        return true;
    if(n == 0)
        return false;
    if (index == 3)
        return false;

    if(sum(arr+1, x-arr[0], n-1, index + 1))
        return true;
    return sum(arr+1, x, n-1, index);
}

最上面的调用从 index = 0 开始。基本上我是想看看是否有一个总和为给定值 x 的三元组。

我是不是漏掉了什么？

Answer 1

首先，T(n) = 2T(n-1) + Const 会使 T(n) 在 O(2^n) 中，而不是 O(n) 中。如果您没有 index == 3 停止条件，这将是运行时。但是这种停止条件会显着减少运行时间。

找到时间复杂度的一种方法是计算递归树中叶子的数量（即达到停止条件的次数）。每个 index == 3 的叶子对应于从 n 个元素中选择 3 个，因此有 C(n, 3) 个这样的节点。带有 n == 0 和 index < 3 的叶子对应于 0、1 或 2 个元素的选择，即 C(n, 0) + C(n, 1) + C(n, 2)。因此叶子的总数是 O(n^3).

由于内部节点的数量（未达到停止条件并因此进行递归调用的调用）大约等于叶子的数量，并且每次调用的 O(1) 工作时间不包括递归调用，总运行时间为 O(n^3).

获得相同结果的另一种方法是考虑 T(n, index):

T(n, 3) = C = O(1)
T(n, 2) = T(n-1, 3) + T(n-1, 2) + C = O(n)
T(n, 1) = T(n-1, 2) + T(n-1, 1) + C = O(n^2)
T(n, 0) = T(n-1, 1) + T(n-1, 0) + C = O(n^3)

Answer 2

假设顶层调用是用index == 0进行的（来自评论），算法是O(n³)。忽略实现细节，更抽象地考虑它在做什么：

它对数组 arr 执行线性扫描，其中
- 对于每个元素 e，它从 e 之后开始对 arr 的尾部执行线性扫描，其中
  - 对于每个元素 f，它从 f 之后开始对 arr 的尾部执行线性扫描，其中
    - 对于每个元素 g，它检查是否 e + f + g == x

边界情况是没有三元组元素总和为 x 的情况，在这种情况下，直到所有扫描都完成，过程才会结束。从该描述中应该清楚，递归等效于三重嵌套循环。

查找该算法的时间复杂度

Finding Time Complexity Of This Algorithm

c

recursion

time-complexity