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

Question

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

编辑:想通了一切。

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

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

请帮助我理解我错在哪里，并提出一种更好地理解/解决这些类型问题的方法。

函数如下:

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 在时间复杂度方面变得不那么重要了。 编辑:有人向我解释说，即使我们使用“免费”，仍然会考虑 malloc(空间 cpmlexity 明智)。

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

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

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

Answer 1

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 它很简单，- 空间复杂度是 sizeof(int) * m - 我们需要分配那么多 - 时间复杂度仅为 m - 我们正在遍历所有 m数组中的元素 arr .

n%2只能是1或 0 , 所以我们可以替换 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)并返回//(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=1 的相反顺序至 i=4 .

我们可以“展开”函数:

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

同时 m和 n接近无限+1或 -1没有任何意义。

空间复杂度是f1(max(m + i, m + n - 1))的空间复杂度，因为 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