c-寻找该算法的时间复杂性

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。因此，树叶的总数是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的情况，在这种情况下，直到所有扫描完成，过程才会结束。从描述中可以清楚地看出，递归等价于三重嵌套循环。