查找否定的遞推關係的時間複雜度

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）。