Java中遞歸算法的時間複雜度

我剛從另一篇文章中得到這個算法，但是我需要知道如何計算這個算法的temporal complexity？我是一名學生，不太瞭解如何去做。Java中遞歸算法的時間複雜度

public static void getSum(int[] numbersArray, int starting, int sum) 
{ 
    if(numbersArray.length == starting) 
    { 
    // Now we print sum here 
    System.out.println(sum); 
    return; 
    } 

    int value = sum + numbersArray[starting]; 

    getSum(numbersArray, starting + 1, value); 
    getSum(numbersArray, starting + 1, sum); 
}

來源

2017-05-30 Yesid Bejarano Camacho

假設numbersArray具有長度5.我假定有人會與starting = 0調用此，即getSum(numbersArray, 0, 0)。現在：

這要打電話getSum(numbersArray, 1, x)兩次。

getSum(numbersArray, 1, x)的每次呼叫都會撥打getSum(numbersArray, 2, x)兩次。

getSum(numbersArray, 2, x)的每次呼叫都會撥打getSum(numbersArray, 3, x)兩次。等等。

當我們到達getSum(numbersArray, 5, x)時，時間是恆定的;我們稱之爲baseTime。

假設我們說T（n）是執行getSum(numbersArray, n, x)的時間。那麼T（5）是baseTime; T（4）= 2 * T（5）; T（3）= 2 * T（4）;等等。這意味着整個通話的時間T（0）= 2 * T（1）= 2 * 2 * T（2）= 2 * 2 * 2 * T（3）= 2 * 2 * 2 * 2 * T（4）= 2 * 2 * 2 * 2 * 2 * T（5）= 2 * 2 * 2 * 2 * 2 * baseTime。這告訴你的是，算法的時間正比於2 ^m其中m是數組的長度。所以答案會寫成O（2 ^m）。

來源

2017-05-30 03:12:24 ajb

Java中遞歸算法的時間複雜度

回答

相關問題