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

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

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

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