尝试计算函数的时间和存储复杂度 (C)

Trying to calculate time and storage complexity for a function (C)

编辑:我想出了如何正确计算时间复杂度,但仍然无法计算出存储复杂度。

编辑:想通了一切。

我尝试解决一道复杂的问题,但失败了。

答案应该是:时间复杂度 - n(m+n),存储复杂度 - m+n。

请帮助我理解我哪里错了,并建议一种方法来更好地understand/solve这些类型的问题。

函数如下:

void f(int n, int m){
     if (n <= 1) {
         int *arr=malloc(m*sizeof(int));
         for (int i=0; i<m; i++) arr[i] = 0;
         free(arr);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

据我所知,"free(arr)" 释放了 malloc 分配的内存,这使得 malloc 在时间复杂度方面变得不那么重要了。 编辑:有人向我解释说,即使我们使用 'free' malloc 仍然被考虑在内(space cpmlexity wise)。

我看到第一个函数调用使函数调用自身 n 次,当发生这种情况时,m 增加了 1 - n 次,所以第一个 func 调用的时间复杂度是 n(m+1) 并且存储复杂度 n- 因为在递归中有 n 次调用函数。编辑:最终弄明白了。

第二个函数调用调用函数 log(n) 次,m 递增 log(n) 次,这使得此调用的时间复杂度为:log(n)(m+1)。 存储 complexity:log(n).

所以总时间复杂度为n(m+1),总存储复杂度为n。

这其实是一个棘手的问题! 第二个函数调用 f(n%2, m+1) 只是调用递归 f 一次,因为它计算了 n 到 2 的提醒,它可以是 1 或 0!在这两种情况下,都返回 f 函数而无需任何进一步的递归调用。 所以不是log n.

函数 f 在 f(n-1, m+1) 中被调用了 n 次,紧接着在 f(n%2, m+1) 中,它将再次被调用一次。如果只考虑n个因素就是O(2n)了。

现在考虑 m 因子,我们会注意到 if 中的循环重复 m 次,并且 m 在每次递归调用时递增 1(并且当它 returns 从递归调用返回时实际上递减!) 所以它将是 (m+n ... m+1) 的总和,即 O(mn+n(n+1)/2)。就是简化后的。

因此,考虑到这两个因素,时间复杂度 是 O(2n+mn+n(n+1)/2) 这实际上在简化后相当于 O(nm+n^2).

关于存储复杂度:第一次调用(m+1)m递增,会持续n次,第二次调用不会继续,所以存储复杂度 将是 O(n+m).

void f(int n, int m){
     if (n <= 1) {
         int *arr=malloc(m*sizeof(int));
         for (int i=0; i<m; i++) arr[i] = 0;
         free(arr);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

让我们重构它:

void f1(int m) {
    int *arr = malloc(m*sizeof(int));
    for (int i = 0; i < m; i++) {
        arr[i] = 0;
    }
    free(arr);
}

void f(int n, int m){
     if (n <= 1) {
         f1(m);
         return;
     }
     f(n-1, m+1);
     f(n%2, m+1);
}

所以对于 f1 它很简单,- space 复杂度是 sizeof(int) * m - 我们需要分配那么多 - 时间复杂度只是 m - 我们正在遍历所有m 数组中的元素 arr.

n%2只能是10,所以我们可以用f(n%2, m+1);代替f1(m+1)

void f(int n, int m){

     if (n <= 1) {
         f1(m); // (1)
         return;
     }

     f(n-1, m+1); // (2)

     f1(m + 1); // (3)
}

现在。如果 n > 1 那么我们调用 f(n-1, ... 直到 n <= 1。对于每个 n > 1,我们按相反的时间顺序调用 f1(m + 1)(因为它在递归调用之后)。当我们到达 n <= 1 时, f1(m) 被调用 m = m(initial) + n(initial) - 1 次。 哦,也许是 n=5 的例子,然后:

  • 初次调用 f(5, m) 所以 n=5
  • n=5,所以我们调用 f(4, m+1) // (2)
  • n=4,所以我们调用 f(3, m+2) // (2)
  • n=3,所以我们调用 f(2, m+3) // (2)
  • n=2,所以我们调用 f(1, m+4) // (2)
  • n=1,所以我们调用 f1(m+4) 和 return // (1)
  • n=2,在 (2) 之后,所以我们调用 f1(m+4) // (3)
  • n=3,在 (2) 之后,所以我们调用 f1(m+3) // (3)
  • n=4,在 (2) 之后,所以我们调用 f1(m+2) // (3)
  • n=5,在 (2) 之后,所以我们调用 f1(m+1) // (3)

我们可以看到 f1(m+4) 被调用了两次,并且我们正在以相反的顺序调用 f1(m + i)i=1i=4.

我们可以"unfold"函数:

void f(int n, int m){
     f1(m + n - 1);
     for (int i = n - 1; i > 0; --i) {
         f1(m + i);
     }
}

由于 mn 都接近无穷大,因此 +1-1 没有任何意义。

space复杂度是f1(max(m + i, m + n - 1))的space复杂度,因为f1每次都释放内存。所以它是 (m + n - 1) * sizeof(int)(m + n) * sizeof(int),即 m + n

时间复杂度取决于我们调用f1函数的次数。我们看到我们调用:

f1(m + n - 1)
f1(m + n - 1)
f1(m + n - 2)
...
f1(m + 2)
f1(m + 1)

所以时间复杂度为

(m + n - 1) + ((m + n - 1) + (m + n - 2) + ... + (m + 1))
(m + n - 1) + (n - 1) * m + ((n - 1) + (n - 2) + ... 1)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
(m + n - 1) + (n - 1) * m + ((n - 1) * (n - 1 + 1) / 2)
// the `*2`, `/2`, `+1` and `-1` mean nothing close to infinity
 m + n      + n       * m + n        *  n
m + n + m * n + n * n
m * (n + 1) + n * (n + 1)
(m + n) * (n + 1)
(m + n) * n