c - 这段代码的 Big-O 是什么？

Question

最近考试的题目是:g的时间复杂度是多少？

int f(int *arr, int n, int m)
{
    if(n == 0)
    {
        if(m == 0)
            return 3;

        return arr[m] + f(arr, n, m - 1);
    }

    return f(arr, n - 1, m);
}

int g(int *arr, int n)
{
    return f(arr, n, n);
}

现在，我和我的大多数 friend 的答案都是 O(n)，因为显然有 2*n 次调用 f 而没有别的，但是教授的答案是 O(n^2)。有人可以向我解释谁是对的吗？如果是他，你能解释一下为什么吗？

Answer 1

编辑:

在后期，我意识到我解决了错误的问题。我正在解决内部函数调用何时为 f(arr, m, m - 1) 的问题。在那种情况下，时间复杂度确实是 O(n²)。问题发布的方式，时间复杂度是O(n)。但是，我将离开这篇文章，因为这很可能也是教授误会的方式。因此，下面的答案是按照考试问题的方式编写的，以供引用。

考虑采取的步骤:

1. 递归调用 f() n 次，这意味着 n == 0 n 向下调用堆栈。
2. 现在，在这个最底层的函数调用中，我们可以输入 if 语句。
3. 我们再次调用 f()，减少 m，但通过将 m 作为第二个参数调用来保持原始 n 值。
4. 在这个“新的”递归堆栈中，我们必须先再次调用 f() n(或 m)次，然后才能将 m 再次减 1。
5. 一旦 m == 0，我们就可以返回。

看看这张图，其中每个“单位”代表对 f() 的一次调用。当 n == 0 时，我们再次调用第三个参数并将 m 减 1，因此我们降低了一个级别。

由于此图中矩形的面积是 n * m 和 m == n，这意味着 f() 是调用了 n² 次，代码的时间复杂度为 O(n²)。