c - 为什么这个函数的空间复杂度是m * n？

为什么这个函数的空间复杂度是m，而不是m * log（n）？
因为在每个递归函数中，它需要从(m*2^i)/2^i = m到i的0和log(n)从到所以它必须是m*logn，这里我缺少什么？

void f3(int n, int m) {
    double *p;
    int i;
    if (n <= 1)
        return;
    p = (double *)malloc(m * sizeof(double));
    if (p == NULL)
        return;
    for (i = 0; i < n; i++)
        if (i < m)
            p[i] = i;
    printf("%f ", p[0]);
    free(p);
    f3(n / 2, m * 2);
    f3(n / 2, m * 2);
}

最佳答案

递归中有一个（近似）不变性：

n * m = (n/2) * (m*2)

因此，当递归深入时，m会变得越来越大，直到n = 1，其中m在开始时是m*n。
你的内存分配只是

p = (double*)malloc(m * sizeof(double));

在进入下一个递归之前，它是freeed。因此最大的m是最大的空间复杂度，即O(mn)。

关于c - 为什么这个函数的空间复杂度是m * n？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49340851/