试图计算函数的时间和存储复杂度（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在时间复杂性方面变得不可思议。编辑：有人解释说，即使我们使用'free'，仍然会考虑malloc（空间cpmlexity明智）。

我看到第一个函数调用使函数调用本身n次，当发生这种情况时，m被整理1 - n次，因此第一个函数调用的时间复杂度为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。 Och，也许是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

Answer 2

这实际上是一个棘手的问题！第二个函数调用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（并且当它从递归调用返回时实际上减少！）所以它将是（m + n ... m + 1）是O（mn + n（n + 1）/ 2）。它简化后。

因此，考虑到这两个因素，时间复杂度为O（2n + mn + n（n + 1）/ 2），其实际上在简化等效于O（nm + n ^ 2）之后。

关于存储复杂性：m对于第一次呼叫（m + 1）递增，其将继续n次但是第二次呼叫不继续，因此存储复杂度将是O（n + m）。