循环内部递归的运行时复杂性

我尝试确定以下代码的运行时复杂性。我想出了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);

来源

2017-08-24 S.H.

声音正确，或多或少 –

Aheum，我没有得到+ n –

在函数中为什么你需要这么多的参数？请给代码添加一些评论 – User27854

我想该函数的递归关系是 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。

希望它有帮助！

来源

2017-08-24 07:01:23 arunk2

循环内部递归的运行时复杂性

回答

相关问题