为什么这个函数的space复杂度是m*n？

Question

为什么这个函数的 space 复杂度是 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);
}

Answer 1

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

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

因此，当你的递归越来越深时，m 会越来越大，直到 n = 1，其中 m 一开始就是 m*n。

你的内存分配只有

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

并且它在进入下一个递归之前被 freeed。所以最大的m是最大的space复杂度，也就是O(mn).