次の再発の時間の複雑さ？

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という2つの問題に分解し、その間に1を費やします。作成した2つの新しい問題は、順番に分割されるなど、あなたがしているのは自分自身でさらに多くの作業を作成することです。