非重叠子问题递归求解的时间复杂度分析
Time Complexity Analysis for Non-ovarlapping Subproblem Recursive Solution
这里我只是放python代码。
Rec(Arr,N,K,X) :
if(X==0 and K==0):
return 1
elif(X<=0 or K<=0 or N<0):
return 0
else :
return Rec(Arr,N-1,K,X)+Rec(Arr,N,K-1,X-Arr[N])
假设Arr的所有元素都是不同的，这就得出所有子问题都是不重叠的（只是拿了一个小案例，手动做）
请根据 N、K、X 评估时间复杂度。
感谢阅读这个问题...
基本上这个问题被认为是高度以max(N,K)为界的二叉树的深度优先搜索。所以时间复杂度的顺序受限于 2^max(N,K)。然后 X 和 Arr 可能会降低这个时间复杂度。但不清楚，因为它取决于 Arr 和 X 的值。 （例如，如果 Arr=[inf,...,inf]，时间复杂度将为 N。）
这里我只是放python代码。
Rec(Arr,N,K,X) :
if(X==0 and K==0):
return 1
elif(X<=0 or K<=0 or N<0):
return 0
else :
return Rec(Arr,N-1,K,X)+Rec(Arr,N,K-1,X-Arr[N])
假设Arr的所有元素都是不同的，这就得出所有子问题都是不重叠的（只是拿了一个小案例，手动做）
请根据 N、K、X 评估时间复杂度。 感谢阅读这个问题...
基本上这个问题被认为是高度以max(N,K)为界的二叉树的深度优先搜索。所以时间复杂度的顺序受限于 2^max(N,K)。然后 X 和 Arr 可能会降低这个时间复杂度。但不清楚，因为它取决于 Arr 和 X 的值。 （例如，如果 Arr=[inf,...,inf]，时间复杂度将为 N。）