algorithm - 找出给定的负递归关系的时间复杂度

Question

递归关系的时间复杂度是多少
T(n) = T(n-3) + T(n-2) - T(n-1) 如果 n>3 否则 T(n)=n

Answer 1

我认为您的 T 不能表示时间复杂度，因为它的许多值都是负数。我假设您的问题实际上是“T 的复杂性是什么”。

你的递归关系的解，对于 n>3 是 T(n) = n 如果 n 是奇数，4-n如果 n 是偶数。

归纳很简单:对于偶数 n

T(n) = T(n-3) + T(n-2) - T(n-1)
     = n-3 + 4-(n-2) - (n-1)
     = 4 - n

对于 n 奇数:

T(n) = T(n-3) + T(n-2) - T(n-1)
     = 4-(n-3) + n-2 - (4 - (n-1))
     = 4 - n + 3 + n - 2 - 4 + n - 1
     = n

并且基本情况需要检查 T(4)、T(5)、T(6)，它们分别是 0、5、-2。

因此 T(n) = O(n)。