algorithm - 次の再帰の時間の複雑さ?

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ます。

数学的帰納法で証明してみよう

基本

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