以下復發的時間複雜性？

Question

找出重複發生的時間複雜度（Big Oh Bound）T(n) = T(⌊n⌋) + T(⌈n⌉) + 1。

這樣的時間複雜度如何出來是O(n)？

Answer 1

您可能需要T(n)=T(⌊n/2⌋)+ T(⌈n/2⌉) + 1。

讓我們計算T(n)的前幾個值。

T(1) = 1 
T(2) = 3 
T(3) = 5 
T(4) = 7 

我們可以猜到T(n) = 2 * n - 1。

允許證明由mathematical induction

基礎

T(1) = 1 
T(2) = 3 
T(3) = 5 
T(4) = 7 

歸納步

T(2*n) = T(⌊2*n/2⌋)+ T(⌈2*n/2⌉) + 1 
    = T(⌊n⌋)+ T(⌈n⌉) + 1 
    = (2*n - 1) + (2*n - 1) + 1 
    = 4*n - 1 
    = 2 * (2*n) - 1 

T(2*n+1) = T(⌊(2*n+1)/2⌋)+ T(⌈(2*n+1)/2⌉) + 1 
    = T(n)+ T(n+1) + 1 
    = (2*n - 1) + (2*(n+1) - 1) + 1 = 
    = 4*n + 1 = 
    = (2*n+1)*2 - 1 

由於兩個基礎和感應步驟已被證明的是，現在已經證明用數學歸納法T（n）適用於所有自然2 * n - 1。

T(n) = 2*n - 1 = O(n)

Answer 2

你目前沒有任何意義。由於n通常被認爲是一個自然數，所以n=⌊n⌋=⌈n⌉。再次發現：將尺寸爲n的問題分解爲尺寸爲n的兩個問題，並花費時間1這樣做。您剛創建的兩個新問題將依次進行拆分，等等 - 您所做的只是爲自己創造更多的工作。