确定recursion函数的复杂性（大O符号）
我明天有一个计算机科学中期，我需要帮助确定这些recursion函数的复杂性。 我知道如何解决简单的案例，但是我仍然在努力学习如何解决这些困难的案例。 这些只是我无法弄清的几个例子问题。 任何帮助将不胜感激，并将大大有助于我的学习，谢谢！
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); } 大O符号的时间复杂度，按照数字顺序排列：
- 第一个函数在达到基本情况之前被recursion地调用n次，所以它的
O(n)通常被称为线性函数 。 - 第二个函数每次调用n-5，所以我们在调用函数之前从n中减去5，而n-5也是
O(n)。 （实际上被称为n / 5次，并且，O（n / 5）= O（n））。 - 这个函数是log（n）的基数为5，每次我们在调用函数之前除以5，所以它的
O(log(n))（基5），通常被称为对数 ，最经常的大O符号和复杂性分析使用基数2 。 - 第四，它是
O(2^n)或指数的 ，因为每个函数调用自己调用两次，除非它被recursion了n次。 -
至于最后一个函数，for循环占用n / 2，因为我们增加了2，而recursion占用了n-5，因为for循环是recursion调用的，所以时间复杂度是（n-5）*（n / 2）=（2n-10）* n = 2n ^ 2- 10n，由于渐近行为和最坏情况的考虑或者大O争取的上界，我们只关注最大项
O(n^2)。祝你好运;）
对于n <= 0 ， T(n) = O(1) 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是一些常数
通过归纳：
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)
我们可以通过归纳certificateT(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) 。
我发现用于近似recursionalgorithm的复杂性的最好方法之一是绘制recursion树。 一旦你有recursion树：
Complexity =length of tree(root node to leaf node) * number of leaf nodes
- 第一个函数的长度为
n，叶节点数为1因此复杂度为n*1 = n -
第二个函数的长度为
n/5，叶节点的数量为1因此复杂度为n/5 * 1 = n/5。 它应该近似于n -
对于第三个函数，由于
n在recursion调用时被除以5，所以recursion树的长度将是log(n)(base 5)，并且叶节点的数目也是1，因此复杂度将是log(n)(base 5) * 1 = log(n)(base 5) -
对于第四个函数，由于每个节点都有两个子节点，所以叶节点的数量等于
(2^n)，recursion树的长度为log n因此复杂度为(2^n) * log n。 但是由于log n在log n是不重要的，所以可以忽略，复杂度只能说是(2^n)。 -
对于第五个function来说，有两个元素介绍了复杂性。 由函数的recursion性质和由每个函数中的
for循环引入的复杂性引入的复杂性。 通过上面的计算，由函数的recursion性质引入的复杂性将是〜n，并且由于循环n复杂性。 总复杂度将是n*n。
注意：这是计算复杂性的快速和肮脏的方法（没有官方的！）。 很想听到这方面的反馈。 谢谢。
