ループ内の再帰の実行時の複雑さ

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（2 ^N）であるO（N！）あります。 More details。

希望すると助かります！