計算遞歸算法的時間複雜度。

我剛剛開始解決Topcoder算法問題，並在Java中爲SRM 466 Div 2 LotteryTicket問題編寫了此算法。計算遞歸算法的時間複雜度。

由於我對時間複雜性不太好，所以如果有人能解釋我如何一步一步計算這個算法的時間複雜度。

public static String buy1(int price,int...b){ 
    int sum=0; String stat="IMPOSSIBLE"; 

    for(int i=0;i<b.length;i++) 
     sum=sum+b[i]; 

    if(sum==price) 
     return "POSSIBLE"; 

    if(b.length>1){ 
     stat=buy1(price,Arrays.copyOfRange(b,0,b.length-1)); 
     stat=buy1(price,Arrays.copyOfRange(b,1,b.length)); 
    } 

    return stat; 
}

來源

2012-09-12 Aman Sharma

可以使用遞歸樹的方法，掌握方法找到的複雜性。

查詢this瞭解更多關於如何解決這個問題的想法。

作爲一個額外的練習嘗試使用此計算合併排序的複雜性。

來源

2012-09-12 07:06:26

有趣的問題。讓我們正確地計算它;）因此，我們將檢查條件（sum == price）永不會出現的最壞情況。

首先讓我們來看看complecity時將b.length = 1，那麼你應該使用週期內僅只有一個「=」操作：

for(int i=0;i<b.length;i++)

而且2內初始化：

int sum=0; String stat="IMPOSSIBLE";

下一頁步。讓我們計算一下N的任務。首先你需要在循環的第一個內部執行N「=」操作，在內部初始化的時候執行2個操作，在內部執行2個操作。

stat=buy1(price,Arrays.copyOfRange(b,0,b.length-1)); 
    stat=buy1(price,Arrays.copyOfRange(b,1,b.length));

另一個操作是在遞歸步驟內進行的。所以我們可以使用反覆式針對這種情況，其等於：

F（N）= 4 + N + 2 * F（N-1），F（1）=該方程的3

解決方案是： f（n）= - 6 + 5 * 2^nn

所以你的算法的擴展性是指數的。 O（2^n）我忽略了除「=」之外的所有其他操作，因爲它們不會改變漸近複雜性。

來源

2012-09-12 11:20:49 Gloomcore

對於你的情況，復發關係（讓b.length個（）是BN）

     ___________buy1(p,bn-1) (as (b,0,b.length-1) equivalent is bn-1 in number) 
        /
    buy1(p,bn) ____/ 
        \ 
        \___________ buy1(p,bn-1) (as (b,1,b.length) equivalent is bn-1 in number)

所以我們對N-1因此，我們的時間函數T N =兩個子問題的問題（ n）如下

T(n)=2T(n-1)+c (For convenience lets eliminate c as it is very less compared to T(n) for this instance) 
    T(n)=2[2(T(n-2))] 
    T(n)=2{2[2(T(n-3))]} ===> 2poweri(T(n-i)) -------- equation(1)

當符合基本條件時，重現結束。對於基礎條件，假設t（0）= c（是基礎條件），意味着t（ni）= t（0）。 {t（0）}

所以我們的時間函數值是2power（n），我們的程序複雜度等於bigoh（2power（n））

來源

2012-09-12 12:29:49 Imposter

計算遞歸算法的時間複雜度。

回答

相關問題