algorithm - 带循环的递归函数的时间复杂度

Question

以下函数的时间复杂度是多少？

int f = (int n) => {
  if (n === 1) {
    return 1;
  }

  for (let i = 0; i < n; i++) {
    console.log(i);
  }

  return f(n-1) + f(n-1)
}

这是递归树的样子，其中i表示深度:

                   f(4)                         // i = 0
                  /    \
                /        \
              /            \
            /                \
          /                    \
        f(3)                  f(3)              // i = 1
       /   \                  /   \
     /       \              /       \
   f(2)      f(2)         f(2)      f(2)        // i = 2
  /   \     /   \        /   \     /   \
f(1) f(1) f(1) f(1)    f(1) f(1) f(1) f(1)      // i = 3

如果函数内部没有循环，时间复杂度将为 O(2^n)。但是现在有一个循环所以:

在每个深度，进行的函数调用次数是 2 ^ i 并且在每个函数调用中 n - i 迭代是在循环中完成的，因此在每个级别(2 ^ i) * (n - i) 操作正在完成。因此，时间复杂度可以计算为:

T(n) = [(2 ^ 0) * (n - 0)] + [(2 ^ 1) * (n - 1)] + [(2 ^ 2) * (n - 2)] + ... + [(2 ^ (n - 1)) * (n - (n - 1))]

那么我的看法是否正确，最终的时间复杂度可能是多少？

Answer 1

你是对的，日志调用的数量是由重复驱动的

T(n) = C1 n + C2 + 2 T(n-1)

T(1)=C3。

我们可以猜测解的形式为

T(n) = A 2^n + B.n + C

并通过识别，

T(n) = A 2^n - C1 n - C2 + C1. 

最后，

T(1) = 2 A - C2 = C3

给出 A。