在循环中可变调用的递归函数的时间复杂度

Question

这个函数的时间复杂度是多少：

 public int calculate(int[] arr, int index) {
  int max = 0, sum = 0;
  for (int i = index; i < arr.length && i < index + arr[index]; i++) {
    sum += arr[i];
    max = Math.max(max, calculate(arr, i + 1));
  }
  return Math.max(max, sum);
}

使用数组和索引调用该函数。由于函数对自身进行 arr[index] 递归调用，我们可以说它的时间复杂度是 O(max(arr)^n) （'n' 是 arr 中元素的数量）吗？是否有可能找到更严格的限制？时间复杂度肯定不是2^n吧？

Answer 1

让我们首先从循环条件中删除 i < index + arr[index] 部分，这只会（有时）减少迭代次数。通过删除它，我们可以得到最坏的情况。

在每次循环迭代中都会调用函数，计算函数执行的次数（在任何递归深度）是衡量时间复杂度的一个很好的方法。我们称此计数为 c。

现在定义k为不考虑递归的循环迭代次数，所以k为arr.length - i

c依赖于k，所以说c_k

对于k = 0没有迭代，所以只有单次调用，所以c₀ = 1 。我们可以继续增加 k:

c₁ = 1 + c₀ = 2
c₂ = 1 + c₀ + c₁ = 2c₁ = 4
c₃ = 1 + c₀ + c₁ + c₂ = 2c₂ = 8
...
c_k = 1 + ∑^k-1_i=0(c_i) = 1 + ∑^k-2_i=0(c_i) + c_k-1 = 2.c_k-1 = 2^k

当你用 i=0 调用函数时，定义 n 为 arr.length 那么结论是函数的时间复杂度为 O(2ⁿ)

在循环中可变调用的递归函数的时间复杂度

Time complexity of a recursive function called variably in a loop

algorithm

recursion

complexity-theory

big-o

time-complexity