具有两个变量的递归函数的时间复杂度

Question

我有一个递归函数，它接受两个变量然后分成两个调用：

def f(n, m):
    if ((n == 0) or (m == 0)):
        return 1

    return f(n - 1, m) + f(n, m - 1)

前三个递归调用如下所示：

                    f(n-2, m)
                   /
          f(n-1, m)
         /         \
        /           f(n-1, m-1)
       /
f(n, m)
       \
        \           f(n-1, m-1)
         \         /
          f(n, m-1)
                   \
                    f(n, m-2)

我知道分成两个调用的函数将具有 O(2^n) 的指数时间复杂度，但我怎样才能同时包含第二个参数及其条件？

Answer 1

您传递给每个函数的内容不会改变时间复杂度。

Big O 应该是最坏的情况，而不是最好的情况。或者至少，常见情况。如果你按字母顺序将项目放入二叉树中，它的性能将是 O(n)，而不是 O(log2 n)。但是没有人说二叉树中的插入性能是 O(n)，因为这不是常见的情况。