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

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ⁿ)