アルゴリズムの実行時間は？

Question

分割征服アルゴリズムは、それぞれサイズn-1の2つのサブ問題に分割してサイズnの問題を解決し、その解を結合するためにO（n）時間かかる。このアルゴリズムのランタイムは何ですか？

私はこの漸化関係をどのように構造化し、ランタイムが何であるかを判断する方法についてはあまりよく分かりません。次の関係は正しいですか？もしそうなら

T（N）= 2T（N-1）+ O（n）の

は、どのように私は、このことからランタイムを得ることができますか？

ありがとうございました！

Answer 1

はい、繰り返しの関係で問題が正しく記述されています。それは+nいうより+O(n)です（T(n) = 2T(n-1) + n

次に、漸化式を入れ子式（およびT（0）= 0）

T(n) = n + 2(n-1) + 4(n-2) + 8(n-3) + ... + 2^n(n-n) 
    = (1 + 2 + 4 + ... + 2^n)n - (0*2^0 + 1*2^1 + ... + n*2^n) 
    = n*(2^(n+1)-1) - 2(n*2^n-2^n+1) 
    = 2^(n+1) - n - 2 

チェックを想定して：物事がコンクリートにするために、のは、漸化式があるとしましょう。これは正しいです：

2T(n-1) + n 
    = 2(2^n - (n-1) - 2) + n 
    = (2^(n+1) - 2n + 2 - 4) + n 
    = 2^(n+1) - n - 2 
    = T(n)