不能帶有單環

找到遞歸函數的時間複雜度以下是。我已經作出了遞推方程這樣不能帶有單環

T（n）的一個簡單的遞歸功能= KT（N-1）+1

我已經對int i使用了+ 1;我已經解決了這樣的問題

T（n）= kT（n-1）+1。。。 T（N）= K^MT（納米）+米

爲了使T（1） - >納米= 1 - >中m = n-1

它變爲（K^N-1）（N -1）

現在我的問題是，是否好。我期待它n^2，但這似乎不是多項式。

void permute(int k,int size) 
{ 
    int i; 
    for (i=k-1;i>=0;i--) 
    permute(k-1,size); 
    return; 
}

請幫助我如何解決這個問題的短

來源

2013-08-04 Charlie

什麼是'尺寸'？它似乎並沒有被使用。 – Geobits

@Geobits我沒有寫過函數 – Charlie

好吧，就像它寫的那樣，它不會*做任何事情。這只是一個空循環。 – Geobits

設n =大小。然後

T(n,k)=k*T(n,k-1) + O(1) 
    =k*[(k-1)*T(n,k-2) + O(1)] + O(1) 
    =k*(k-1)*T(n,k-2) + k*O(1) + O(1) 
    =k*(k-1)*[(k-2)*T(n,k-3) + O(1)] + k*O(1) + O(1) 
    =k*(k-1)*(k-2)*T(n,k-3) + k*(k-1)*O(1) + k*O(1) + O(1) 
    =... 
    =O(k!)*T(n,0) + O(1) * [P(k,k-1)+P(k,k-2)+...+P(k,1)] 
    =O(k!)*T(n,0) + O(1) * e * O(k!) 
    =O(k!)*T(n,0)

所以它取決於permute（0，size）的複雜性。

來源

2013-08-05 02:04:52

不能帶有單環

回答

相關問題