java - 循环内递归的运行时复杂度

Question

我尝试确定以下代码的运行时复杂性。我想出了 T(n) = n * T(n-1) + n 其中 T(0) = 1 但不确定它是否正确以及如何解决。

private void myFunction(int[] nums, int startIndex, int target) {
    if (target == 0) {
        // do something
    }
    if (target <= 0 || start > nums.length) {
        return;
    }

    for (int i = startIndex; i < nums.length; i++) {
        myFunction(nums, i+1, target-nums[i]);
    }
}

myFunction(nums, 0, target);

Answer 1

我猜函数的递推关系是 T(n) = n * T(n-1) + O(1)，其中 T(0) = 1

减少:

T(n) 
= n * T(n-1) + O(1)
= n * (n-1) * T(n-2) + 1 + 1
= n * (n-1) * (n-2) * T(n-3) + 1 + 1 + 1
...
= n * (n-1) * (n-2) * (n-3) ... T(0) + n * 1 (n times)
= n! + n

因此，函数的整体复杂度为 O(n!)，大​​于 O(2ⁿ)。 More details .

希望对你有帮助!