确定递归函数的复杂性（大O表示法）
我明天有计算机科学中期课程，我需要帮助来确定这些递归函数的复杂性。 我知道如何解决简单的案例，但我仍在努力学习如何解决这些困难的案例。 这些只是我无法弄清楚的一些示例问题。 任何帮助将不胜感激，并会对我的学习有很大帮助，谢谢！
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, %dn",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符号的时间复杂度，按照数字顺序排列：
O(n)通常称为线性函数 。 O(n) 。 （实际上称为n / 5次的顺序，并且，O（n / 5）= O（n））。 O(log(n)) （基数5），通常被称为对数并且最经常的大O符号和复杂度分析使用基数2 。 O(2^n)或指数 ，因为每个函数调用自己调用两次，除非它被递归了n次。 至于最后一个函数，for循环占用n / 2，因为我们增加了2，递归取n-5，因为for循环被递归调用，所以时间复杂度为（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)
我们可以通过归纳证明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) 。
我发现用于近似递归算法复杂性的最佳方法之一是绘制递归树。 一旦你有了递归树：
Complexity = length of tree from root node to leaf node * number of leaf nodes
n ，叶节点1数量为n*1 = n 第二个函数的长度为n/5 ，叶节点的数量为1因此复杂度为n/5 * 1 = n/5 。 它应该近似于n
对于第三个函数，由于n在每次递归调用时被除以5，所以递归树的长度将是log(n)(base 5) ，并且叶节点的数量再次为1，因此复杂度将是log(n)(base 5) * 1 = log(n)(base 5)
对于第四个函数，由于每个节点将有两个子节点，叶节点的数量将等于(2^n)并且递归树的长度将是n因此复杂度将是(2^n) * n 。 但由于n在(2^n)前面不显着，所以可以忽略，复杂度可以说只是(2^n) 。
对于第五个函数，有两个元素介绍复杂性。 复杂性由函数的递归性质和由每个函数中的for循环引入的复杂性引入。 做上述计算中，通过函数递归性质带来的复杂性将是~ n和复杂性由于for循环n 。 总复杂性将是n*n 。
注意：这是计算复杂性的快速和肮脏的方式（没有官方的！）。 很想听到关于此的反馈。 谢谢。
链接地址: http://www.djcxy.com/p/39701.html上一篇: Determining complexity for recursive functions (Big O notation)