时空算法复杂度

Question

我正在为一个编码问题编写蛮力方法--我需要用最大步长k来计算数组中的最大得分路径。

输入:num= 1，-1，-2,4，-7,3，k=2输出:7解释:您可以选择形成子序列1，-1,4,3。总数是7。

我遇到了计算复杂性的问题。我的想法是，在每个项目上，我们可以调用函数k次，因此时间和空间是O(k^n)，其中n是数组的长度。我的第二个猜测:对于第一个元素，我们最多调用1次函数，第二次调用2次(即k> i)等等。因此，我们有和1+2+…+k+k+…+k=(1+ k) / 2)k +(k+ k) / 2) /(N)= O(k^2)。我认为第一个是正确的，但我不能确定原因:/

以下是我的Java代码：

public int maxResult(int[] nums, int k) {
    return maxResult(nums, k, nums.length - 1);
}

private int maxResult(int[] nums, int k, int index) {
    if (index == 0)
        return nums[0];
    int max = Integer.MIN_VALUE;
    int start = index - k < 0 ? 0 : index - k;
    
    for ( int i = start; i < index; i++ ) {
        int res = maxResult(nums, k, i);
        System.out.println(i);
        max = Math.max(res, max);
    }
    return max + nums[index];
}

Answer 1

对于特定k的代码，递归关系是

C(n) = sum(C(n-i) for i = 1...k) for n>k
C(n) = C(1) + C(2) + ... + C(n-1) for n <= k
C(1) = 1

这是高阶斐波那契数的递推关系，它被k-1位移动.即C(n) = kFib(k，n+k-1)。k-Fibonacci数随Theta( alpha ^n)的增长而增长，其中α是基于k-的常数，对于k=2，α是黄金比率，随着k的增加，α越来越接近2。(具体来说，alpha是(x^k - x^(k-1) -…-x-1)的正根)。

因此C(n) = kFib(k，n+k-1) =Theta(α^(n+k))。

因为alpha总是小于2，所以O(2^(n+k))是一个简单的正确界，虽然不是紧的。