確定遞歸函數的複雜性（大O表示法）

Question

明天我有計算機科學中期，我需要幫助來確定這些遞歸函數的複雜性。我知道如何解決簡單的案例，但我仍在努力學習如何解決這些困難的案例。這些只是我無法弄清楚的一些示例問題。任何幫助將不勝感激，並會對我的學習有很大幫助，謝謝！

int recursiveFun1(int n) 
{ 
    if (n <= 0) 
     return 1; 
    else 
     return 1 + recursiveFun1(n-1); 
} 

int recursiveFun2(int n) 
{ 
    if (n <= 0) 
     return 1; 
    else 
     return 1 + recursiveFun2(n-5); 
} 

int recursiveFun3(int n) 
{ 
    if (n <= 0) 
     return 1; 
    else 
     return 1 + recursiveFun3(n/5); 
} 

void recursiveFun4(int n, int m, int o) 
{ 
    if (n <= 0) 
    { 
     printf("%d, %d\n",m, o); 
    } 
    else 
    { 
     recursiveFun4(n-1, m+1, o); 
     recursiveFun4(n-1, m, o+1); 
    } 
} 

int recursiveFun5(int n) 
{ 
    for (i = 0; i < n; i += 2) { 
     // do something 
    } 

    if (n <= 0) 
     return 1; 
    else 
     return 1 + recursiveFun5(n-5); 
} 

Answer 1

的時間複雜度，在大O符號，對於每個功能，是按數字順序：

1. 第一功能是被稱爲遞歸n次到達基地情況之前，所以其O(n)，通常被稱爲線性。
2. 第二個函數每次調用n-5，所以我們在調用函數前從n中減去5，但是n-5也是O(n)。 （實際上稱爲n/5次的順序，並且，O（n/5）= O（n））。
3. 此功能的log（n）基地5，對於我們每次調用函數所以它O(log(n))（基地5）之前除以5 時間，通常被稱爲對數和最經常大O符號和複雜性分析使用基地2 。
4. 在第四，這是O(2^n)，或指數，因爲除非它已經被遞歸ň次，每次函數調用調用本身兩次。

5. 至於最後一個函數，for循環佔用n/2，因爲我們增加了 2，遞歸取n-5，因爲for循環遞歸地被稱爲 ，因此時間複雜度爲（n -5）*（n/2）=（2n-10）* n = 2n^2- 10n，由於漸近行爲和最壞情況的情況考慮或大O爭取的上限，我們只關注最大的期限如此O(n^2)。

   您期中好運;）

Answer 2

對於情況n <= 0，T(n) = O(1)。因此，時間複雜度將取決於何時n >= 0。

我們將在下面的部分考慮n >= 0的情況。

1.

T(n) = a + T(n - 1) 

其中a是一些恆定。

通過感應：

T(n) = n * a + T(0) = n * a + b = O(n) 

其中a，b是常數一些。

2。

T(n) = a + T(n - 5) 

其中a是一些恆定

通過感應：

T(n) = ceil(n/5) * a + T(k) = ceil(n/5) * a + b = O(n) 

其中a，b是常數一些和k < = 0

3.

T(n) = a + T(n/5) 

其中a是一些c onstant

通過感應：

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n) 

其中a，b是常數一些

4.

T(n) = a + 2 * T(n - 1) 

其中a是一些恆定

通過感應：

T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2^n 
    = a * 2^(n+1) - a + b * 2^n 
    = (2 * a + b) * 2^n - a 
    = O(2^n) 

其中a，b是一些常數。

5.

T(n) = n/2 + T(n - 5) 

我們可以通過感應證明T(5k) >= T(5k - d)其中d = 0，1，2，3，4

寫n = 5m - b（M，b是整數; b = 0，1 ，2，3，4），然後m = (n + b)/5：

T(n) = T(5m - b) <= T(5m) 

（實際上，要更嚴格這裏，新的功能T'(n)應該被定義爲使得T'(5r - q) = T(5r)其中q = 0, 1, 2, 3, 4。我們知道如上所述T(n) <= T'(n)。當我們知道T'(n)在O(f)，這意味着存在恆定的a，b使得T'(n) <= a * f(n) + b，我們可以推導出T(n) <= a * f(n) + b，因此T(n)在O(f)。這一步是不是真的有必要，但它更容易認爲當你沒有對付剩餘）

擴大T(5m)：

T(5m) = 5m/2 + T(5m - 5) 
     = (5m/2 + 5/2) * m/2 + T(0) 
     = O(m^2) = O(n^2) 

因此，T(n)是O(n^2)。

Answer 3

我發現的用於近似遞歸算法複雜性的最佳方法之一是繪製遞歸樹。一旦你的遞歸樹：

Complexity = length of tree from root node to leaf node * number of leaf nodes 

1. 第一個函數將有n長和葉節點1的數量如此複雜性將是n*1 = n

2. 第二個函數將有n/5和數量的長度葉節點再次1所以複雜度將是n/5 * 1 = n/5。應當近似於n

3. 對於第三功能，因爲n正在由5上的每個遞歸調用劃分，遞歸樹的長度將是log(n)(base 5)和葉節點的數目再次1，因此複雜性將是log(n)(base 5) * 1 = log(n)(base 5)

4. 對於第四個函數，由於每個節點將有兩個子節點，所以葉節點的數量將等於(2^n)，並且遞歸樹的長度將爲n，因此複雜度將爲(2^n) * n。但由於n在(2^n)之前不重要，所以可以忽略，複雜度可以說只有(2^n)。

5. 對於第五個函數，有兩個元素引入了複雜性。由函數的遞歸性質和由每個函數中的for循環引入的複雜性引入的複雜性。通過上述計算，函數的遞歸性質引入的複雜性將爲~ n，並且由於循環n而導致的複雜性。總的複雜性將是n*n。

注意：這是計算複雜性的快速和骯髒的方法（沒有官方的！）。很想聽到關於此的反饋。謝謝。