确定递归函数的复杂度(大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, %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);
}
411562 次浏览
小开
最佳答案

每个函数的时间复杂度，用大O表示:

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

这个函数在到达基本情况之前被递归调用n次，因此它的O(n)，通常称为线性。

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)).

int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
这个函数是log(n)以5为底，每除以5一次 在调用函数之前，它的O(log(n))(以5为基数)，通常称为对数，最常见的是大O符号，复杂度分析使用以2为基数 
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);
}
}

在这里，它是O(2^n)或指数，因为每个函数调用都会调用自己两次，除非它已经被递归n次。


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循环是递归调用的，因此，时间复杂度是

(n/5) * (n/2) = n^2/10，

由于渐近行为和最坏情况的考虑或大O正在争取的上限，我们只对最大的项感兴趣，所以O(n^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是某个常数

归纳:

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-1) * a + T(0) * 2^n
= a * 2^n - a + b * 2^n
= (a + b) * 2^n - a
= O(2 ^ n)

其中a b是某个常数。

5.

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

n是某个常数

重写n = 5q + r，其中q和r是整数，r = 0,1,2,3,4

T(5q + r) = (5q + r) / 2 + T(5 * (q - 1) + r)

我们有q = (n - r) / 5，和since r <5，我们可以认为它是一个常量，所以q = O(n)

归纳:

T(n) = T(5q + r)
= (5q + r) / 2 + (5 * (q - 1) + r) / 2 + ... + r / 2 +  T(r)
= 5 / 2 * (q + (q - 1) + ... + 1) +  1 / 2 * (q + 1) * r + T(r)
= 5 / 4 * (q + 1) * q + 1 / 2 * (q + 1) * r + T(r)
= 5 / 4 * q^2 + 5 / 4 * q + 1 / 2 * q * r + 1 / 2 * r + T(r)

由于r <4，我们可以找到某个常数b，使得b >= T(r)

T(n) = T(5q + r)
= 5 / 2 * q^2 + (5 / 4 + 1 / 2 * r) * q + 1 / 2 * r + b
= 5 / 2 * O(n ^ 2) + (5 / 4 + 1 / 2 * r) * O(n) + 1 / 2 * r + b
= O(n ^ 2)
小开

我发现的估算递归算法复杂度的最好方法之一是画递归树。一旦你有了递归树:

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和for循环带来的复杂度n。总复杂度将为n*n。

注意:这是一种计算复杂度的快速且不规范的方法(不是官方的!)很乐意听到这方面的反馈。谢谢。

小开

我们可以用数学证明，这是我在上面的答案中所遗漏的。

它可以戏剧性的帮助你理解如何计算任何方法。 我建议从上到下阅读它，以充分理解如何做到这一点:

  1. T(n) = T(n-1) + 1这意味着方法完成所需的时间等于相同的方法，但有n-1，即T(n-1)，我们现在添加+ 1，因为它是一般操作完成所需的时间(T(n-1)除外)。 现在，我们将找到T(n-1)，如下所示:看起来我们现在可以形成一个函数可以给我们一些重复，这样我们就能完全理解。我们将把T(n-1) = ...的右边而不是T(n-1)放在方法T(n) = ...中，这将给我们:T(n) = T(n-1-1) + 1 + 1，也就是T(n) = T(n-2) + 2，换句话说，我们需要找到缺少的k: T(n) = T(n-k) + k。下一步是使用n-k并声明T(n-1) = T(n-1-1) + 10，因为在递归的最后，当T(n-1) = T(n-1-1) + 11时，它将精确地使用O(1)。从这个简单的方程，我们现在知道T(n-1) = T(n-1-1) + 12。让我们把k放在我们的最终方法T(n) = T(n-k) + k中，这将给我们:T(n-1) = T(n-1-1) + 15，它正好是T(n-1) = T(n-1-1) + 16或T(n-1) = T(n-1-1) + 17
  2. 等于1。你可以自己测试它，看看你得到O(n)。
  3. T(n) = T(n/5) + 1和之前一样，这个方法完成的时间等于相同方法的时间，但包含n/5，这就是为什么它被绑定为T(n/5)。让我们找到T(n/5)，如1:T(n/5) = T(n/5/5) + 1，即T(n/5) = T(n/5^2) + 1。 让我们把T(n/5)放在T(n)中，进行最终的计算:T(n) = T(n/5^k) + k。和之前一样，n/5^k = 1是n = 5^k，这正好是问5的幂，会给我们n，答案是log5n = k(以5为底的对数)。让我们把我们的发现放在T(n) = T(n/5^k) + k中，如下:T(n) = 1 + logn是O(logn)
  4. T(n) = 2T(n-1) + 1我们这里所拥有的基本上与以前相同，但这一次我们递归调用该方法2次，因此我们将其乘以2。让我们找到T(n-1) = 2T(n-1-1) + 1，也就是T(n-1) = 2T(n-2) + 1。我们的下一个地方，让我们把我们的发现:T(n) = 2(2T(n-2)) + 1 + 1是T(n) = 2^2T(n-2) + 2，给我们T(n) = 2^kT(n-k) + k。让我们通过声明n-k = 1即k = n - 1来找到k。让我们将k放置如下:T(n-1) = 2T(n-1-1) + 10大致是T(n-1) = 2T(n-1-1) + 11
  5. T(n) = T(n-5) + n + 1它几乎与4相同，但现在我们添加了n，因为我们有一个for循环。让我们找到T(n-5) = T(n-5-5) + n + 1，它是T(n-5) = T(n - 2*5) + n + 1。让我们放置它:T(n) = T(n-2*5) + n + n + 1 + 1)，它是T(n) = T(n-2*5) + 2n + 2)，对于k: T(n) = T(n-k*5) + kn + k): n-5k = 1，它是n = 5k + 1，大致是n0。这将给我们:n1，大致是n2。
我现在建议你阅读剩下的答案，这会给你一个更好的视角。 祝你好运赢得那些大O:)

小开

这里的关键是可视化调用树。一旦这样做了，复杂性是:

nodes of the call tree * complexity of other code in the function

后一项的计算方法与我们计算普通迭代函数的方法相同。

相反，完整树的总节点计算为

                  C^L - 1
-------  , when C>1
/   C - 1
/
# of nodes =
\
\
L        , when C=1 (this is special case of a single branch tree)

其中C是每个节点的子节点数，L是树的层数(包括根)。

这棵树很容易形象化。从第一个调用(根节点)开始，然后绘制与函数中递归调用数量相同的子节点数。将传递给子调用的参数写成“节点的值”也是有用的。

下面是上面例子的结果:

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

首先考虑调用树:

n     level 1
n-1   level 2
n-2   level 3
n-3   level 4
... ~ n levels -> L = n

这里每个节点的子节点数为C = 1，层数L = n+1。其余函数的复杂度为O(1)。因此，总复杂度为L * O(1) = (n+1) * O(1) = O (n)

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

这里的调用树是:

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5

C = 1，但L = n/5。其余函数的复杂度为O(1)。因此，总复杂度为L * O(1) = (n/5) * O(1) = O (n)

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

调用树为:

n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)

因此C = 1, L = log(n)。其余函数的复杂度为O(1)。因此，总复杂度为L * O(1) = log5(n) * O(1) = O (log (n))

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);
}
}

这里，调用树更加复杂:

               n                   level 1
n-1             n-1          level 2
n-2     n-2     n-2     n-2      ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3    ...
...                ~ n levels -> L = n

这里每个节点的子节点数为C = 2，而L = n。其余函数的复杂度为O(1)。 这一次我们使用调用树中节点数的完整公式，因为C >1. 因此总复杂性(C ^ l - 1) /(颈- 1)* O (1) = (2 ^ n - 1) * O (1) = O (2 ^ n)。< / p > 

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


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

同样，调用树是:

n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5

这里C = 1, L = n/5。其余函数的复杂度是O(n)因此，总复杂度为L * O(1) = (n/5) * O(n) = O (n ^ 2)

小开

我看到对于公认的答案(recursivefn5)，有些人对解释有问题。所以我要尽我所能来澄清一下

  1. for循环运行n/2次，因为在每次迭代中，我们都将i(计数器)增加2倍。假设n = 10, for循环将运行10/2 = 5次，即当I分别为0、2、4、6和8时。

  2. 在同样的情况下，每次调用递归调用都会减少5倍，即运行n/5次。再次假设n = 10，递归调用运行10/5 = 2次，即当n是10和5时，然后它遇到基本情况并终止。

  3. 计算总运行时间，每次我们调用递归函数时，for循环运行n/2次。由于递归的fxn运行n/5次(在上面的2中)，for循环运行(n/2) * (n/5) = (n^2)/10次，这转换为O(n^2)的整体大O运行时间-忽略常数(1/10)…


提交答案