确定递归函数的复杂度(大 O 表示法) [英] Determining complexity for recursive functions (Big O notation)
问题描述
我明天有一个计算机科学期中考试,我需要帮助确定这些递归函数的复杂性.我知道如何解决简单的案例,但我仍在努力学习如何解决这些更困难的案例.这些只是我无法弄清楚的一些示例问题.任何帮助将不胜感激,并将极大地帮助我的学习,谢谢!
I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve these harder cases. These were just a few of the example problems that I could not figure out. Any help would be much appreciated and would greatly help in my studies, thank you!
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
",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);
}
推荐答案
每个函数的时间复杂度,用 Big O 表示法:
The time complexity, in Big O notation, for each function:
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
这个函数在到达基本情况之前被递归调用 n 次,所以它的 O(n)
,通常称为 linear.
This function is being called recursively n times before reaching the base case so its O(n)
, often called linear.
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
这个函数每次调用n-5,所以我们在调用函数之前先从n中减去5,但是n-5也是O(n)
.(实际上称为 n/5 次的顺序.并且,O(n/5) = O(n)).
This function is called n-5 for each time, so we deduct five from n before calling the function, but n-5 is also O(n)
.
(Actually called order of n/5 times. And, O(n/5) = O(n) ).
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
这个函数是以 5 为底的 log(n),每次除以 5在调用函数之前,所以它的 O(log(n))
(base 5),通常称为 logarithmic 并且最常见的 Big O 表示法和复杂性分析使用 base 2.>
This function is log(n) base 5, for every time we divide by 5
before calling the function so its O(log(n))
(base 5), often called logarithmic and most often Big O notation and complexity analysis uses base 2.
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d
",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
这里是O(2^n)
,或指数,因为每个函数调用都会调用自己两次,除非它被递归n次.
Here, it's O(2^n)
, or exponential, since each function call calls itself twice unless it has been recursed n times.
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
这里for循环需要n/2,因为我们增加了2,递归需要n/5,因为for循环是递归调用的,因此,时间复杂度为
And here the for loop takes n/2 since we're increasing by 2, and the recursion takes n/5 and since the for loop is called recursively, therefore, the time complexity is in
(n/5) * (n/2) = n^2/10,
(n/5) * (n/2) = n^2/10,
由于渐近行为和最坏情况的考虑或大 O 所追求的上限,我们只对最大项感兴趣,所以 O(n^2)
.
due to Asymptotic behavior and worst-case scenario considerations or the upper bound that big O is striving for, we are only interested in the largest term so O(n^2)
.
祝你期中考试好运;)
这篇关于确定递归函数的复杂度(大 O 表示法)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!