非排卵子問題遞歸解決方案的時間複雜性分析

-3

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])

只要編曲的所有元素都是不同的，由此得出結論，所有的子問題是不重疊的（只是把一個小的情況下，做手工）

請評估時間複雜度爲N的， K，X。感謝您閱讀這個問題...

來源

2016-05-12 Ramesh Chandra

我的排隊有什麼問題？每個人都只是低調投票。任何人都可以指出問題？ –

你到底有多複雜？你爲什麼認爲這是不正確的？ –

@ cristiano-sousa我認爲是O（N * K）..我知道這是錯誤的，因爲我得到TLE前提是N <= 50 && K <= 10。感謝＃takoika ..但我不明白他的解決方案..但它給了我一個暗示，這種解決方案將無法正常工作，我不得不尋找更優化的解決方案 –

基本上這個問題被認爲是深度第一次搜索的高度是由max(N,K)界限的二叉樹。所以時間複雜度的順序是以爲界。然後X和Arr可能會降低這個時間複雜度。但目前尚不清楚，因爲它取決於Arr和X的值。（例如，如果Arr = [inf，...，inf]，則時間複雜度將爲N。）

來源

2016-05-12 10:56:13 takoika

你能解釋一下嗎？ –

假設到期X它永遠不會退出..最糟糕的情況..不止 –

2^max（N，K）是沒有X和Arr的上界。 – takoika

非排卵子問題遞歸解決方案的時間複雜性分析

回答

相關問題