algorithm - 算法的时间复杂度

Question

这是我们必须计算给定函数的时间复杂度的问题

f(i) = 2*f(i+1) + 3*f(i+2)
For (int i=0; i < n; i++)
F[i] = 2*f[i+1] 

我认为这个算法的复杂度是 O(2^n) + O(n)，最终是 O(2^n)。如果我错了，请纠正我？

Answer 1

首先，您将来解决这些问题所需的所有信息都在这里。

回答你的问题。因为您没有根据 I 本身提供 f(i) 的定义，所以不可能从您上面写的内容中确定实际的复杂性。然而，一般来说 for 循环像

for (i = 0; i < N; i++) {
    sequence of statements
}

执行 N 次，因此语句序列也执行 N 次。如果我们假设语句是 O(1)，那么 for 循环的总时间是 N * O(1)，总体上是 O(N)。在上述情况下，如果我冒昧地将其重写为

f(0) = 0;
f(1) = 1;
f(i+2) = 2*f(i+1) + 3*f(i)
for (int i=0; i < n; i++)
    f[i] = 2*f[i+2] 

然后我们有一个明确定义的操作序列，并且应该清楚 n 操作的复杂度是，就像我上面给出的示例一样，n * O(1)，即 O(n)。

我希望这有帮助。