對于計算機科學來說，算法至關重要。通俗地講，算法是指解決問題的一種方法或者一個過程。嚴格來講，算法是由若干條指令組成的有序序列，且滿足以下4條性質：

    1.輸入

    2.輸出

    3.確定性

    4.有限性

    算法復雜度的高低體現在運行該算法時所需要的計算機資源的多少上，所需資源越多，算法的復雜度越高，也就稱這個算法較差。因此，算法的復雜度分為時間復雜度和空間復雜度。

    由于空間復雜度是具體算法具體分析，因此這里我們簡單談一談時間復雜度。

    普通函數的時間復雜度大致分為4個步驟：確定循環條件->確定循環變量的變化規律->假設執行了i次->計算i并帶回原方程。

    遵循了上述四個步驟就能求解大部分的算法時間復雜度了。

    對于遞歸函數，我們舉一個簡單的例子來說明。

    這是一個求解大整數乘法的遞歸表達式，對于它的時間復雜度，其計算過程如下：

    T(n)=4T(n/2)+O(n)

    =4[4T(n/4)+O(n/2)]+O(n)=4^2T(n/4)+3O(n)

    =4^2[4T(n/8)+O(n/4)]+3O(n)=4^3T(n/8)+7O(n)

    ......

    =4^xT(n/2^x)+(2^x-1)O(n)//假設執行了x次

    令n=2^x帶入上面方程T(n)=n^2+(n-1)n

    因此時間復雜度為O(n^2)

    再看下面這個

    這是對大整數乘法的另一種優化算法，具體思想我就不再這里贅述了

    對于這個表達式，我們還是按照上面的方法一步一步的來

    T(n)=3T(n/2)+O(n)

    =3[3T(n/4)+O(n/2)]+O(n)=3^2T(n/4)+(3/2+1)O(n)

    =3^2[3T(n/8)+O(n/4)]+(3/2+1)O(n)=3^3T(n/8)+(3^2/2^2+3/2+1)O(n)

    ……

    =3^xT(n/2^x)+(3^x-1/2^x-1+3^x-2/2^x-2+......+3^2/2^2+3/2+1)O(n)

    易知后面括號里其實是首項為1，公比為3/2的等比數列的前n-1項和

    因此上式

    =3^xT(n/2^x)+[4(3^x-1/2^x)-2]O(n)

    令n=2^x，則x=log2(n),帶入

    =3^log2(n)+{4[(3^log2(n/2))/n]-2}O(n)

    =n^log2(3)+4/3(n^log2(3))-2n

    =5/3n^log2(3)-2n

    u因此時間復雜度為O(n^log2(3))=O(n^1.59)

    因為O(n^1.59)

    所以后面這種算法是優于前面那一種算法的。

    你看，都是解決大整數乘法的問題，通過不同的算法，我們求解問題所花的時間也不同，所以，在計算機的發展中，尋找最優算法是一直在路上的。

　以上就是動力節點java培訓機構的小編針對“Java基礎學習：java遞歸函數例子”的內容進行的回答，希望對大家有所幫助，如有疑問，請在線咨詢，有專業老師隨時為你服務。