确定递归函数的复杂性（大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。

注意：这是计算复杂性的快速和肮脏的方法（没有官方的！）。很想听到关于此的反馈。谢谢。