查找否定的递推关系的时间复杂度

Question

这将是递推关系的时间复杂度
T(n) = T(n-3) + T(n-2) - T(n-1) if 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）。