使用递归查找 space 和时间的复杂性

Question

第一个函数：-

void strange (int n,int k)

 {

int i;

if(k > n)

return;

for(i=k; i<n; i++)
  printf("?");

strange(n, k+2);
return;
}

第二个函数：-

void weird(int n, int k)
{

int i;

if(n <= 0 || (k <= 0))
   return;

k *=2;

for(i=0; i < k; i++){

  printf("?");

  weird(n/2, -n/2 )
}
weird(n/2, k)

return;
}

我很难找到两者的复杂性 space 或两者的时间 functions.I 知道我必须在这里使用递归，但我只是不理解递归。我对此很陌生，我的老师只是没有解释 well.Is 有一种简单的方法可以使用递归计算 space 的复杂性和时间？你能告诉我如何处理这类问题吗？

注意：- 我不要求完整的答案只是提示和 advice.So 请不要误解这个 post。

Answer 1

你不使用递归来寻找复杂性，你需要在递归中找到复杂性。我想如果我澄清几件事，你就会明白你需要做什么。

递归

首先，递归只是一个调用自身的函数。非常简单。一个非常简单的递归函数可以用于计数：

recursiveCounter(current, max)
{
  if(current > max)
    return;

  printf("%i ", current);
  recursiveCounter(current + 1, max);
}

这个函数会一直调用自己，直到current大于max，然后returns。

复杂性

现在，就您的复杂性而言，您有两个； space，还有时间。 Space 是您根据输入需要多少内存，而时间是您的函数将执行多少次迭代。在我的示例中，space 复杂度为 O(1)（这是常数），而我的时间复杂度为 O(N)（线性增加）。

另一个例子：

recursiveCounter2(current, max)
{
  if(current >= max)
    return;

  for(int x = 0; x < max; ++X)
  {
    printf("%i ", current);
  }

  printf("\n");

  recursiveCounter(current + 1, max);
}

此函数每次都会从头开始数到给定的数字。输出如下所示：

等等。

放在一起

所以，把它分解成几个部分：

Q.我的递归函数会被调用多少次？

A. 因为我的比较(current < max)和我的线性增长(current + 1)，我们可以假设它会运行 max 次。

Q.我会在函数内部迭代多少次？

A. for 循环还将执行 max 次操作。

综合这些因素，我们将执行 max * max 计算。这使它成为一个 O(N^2) 算法。因此，如果 max 为 5，我们有 5 * 5 = 25 次计算。

将您的问题逐个分解是解决此问题的最佳方法。

Answer 2

第一个函数：

您正在运行建立一个从 k 到 n 的循环，在最坏的情况下将从 0 开始到 n（假设 k 和 n 始终为正数）。

每次递归，您都将两个整数移近完成，运行循环比上一个少两倍。这只会增加复杂性的常数倍数。

所以本质上，对于最坏的情况，您将循环运行n 次，然后是 n-2 次，然后是 n-4 次，依此类推。 k 对时间复杂度没有影响。如果有的话，它会减少运行ning 时间，但大 O 符号会丢弃它。

第二个函数：

for循环运行s k次。 for 循环中的函数是无用的，因为它会 return 一旦调用 if 条件（-ve 的 k 值）。

n 每次递归都减半。要计算这种递归的时间复杂度，您可以将其视为 T(n) = T(n/2) 和 T(1) = 1

即运行值为 n 的递归所花费的时间与运行值为 n/2 的递归所花费的时间相同。而当n减为1时，就是一次O(1)的执行。

求解递归方程以获得递归调用的时间复杂度。

函数本身的时间复杂度是 for 循环的时间复杂度与递归的时间复杂度的乘积。

Space 复杂度： 这两个函数都只有整数变量。没有arrays/strings.

使用递归查找 space 和时间的复杂性

Finding complexities of space and time using recursion

algorithm

complexity-theory