なぜ再発アルゴリズム

Question

QUESTION

への代替T（1）私は、アルゴリズムの複雑さを見つけようとしているときに我々はビッグOを推測することができます。アルゴリズムは、再帰的サイズN-1二部分問題を解決した後、時定数の溶液を組み合わせることによって、サイズNの問題を解決します。

だから、私は再発を書く：

T(n) = 2 * T(n-1) + 1 * O(1) 
    = 4 * T(n-2) + 3 * O(1) 
    = 8 * T(n-3) + 7 * O(1) 
    = 2^k * T(n-k) + ((2^k)-1) * O(1) 

私はので、私はいくつかGoogleで検索します、この時点で立ち往生。例のほとんどは、T（N-K）はT（1）なる作るN-1とKを代用します。その後

T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1) // substitute k with n - 1 

問題は、彼らがこの再発のビッグOを締結O(2^(n-1))です。

私はとても混乱しています。私は知らない

（i）私はまだT(1)の複雑さを知っていますか？

（ⅱ）T(1)が結論と私たちは、この式T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1)からビッグOを見つけることができますどのように

（III）に関連していますか。

ご協力いただければ幸いです。

Answer 1

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

ここで、T（1）は常に一定である。）は、kの大きな値に対して、入力サイズがn > kの時間複雑度を意味します。ここで、nがある定数、例えばn = 5の場合、アルゴリズムの時間複雑度は一定です。 n = 5のアルゴリズムを実行するためには同じ時間がかかるでしょう。

時間の複雑さでは、関数の増加を測定することを忘れないでください。今、nの一定値に対する成長は一定である。このロジックの場合T(1) = constant。

この考え方は、配列の中央値を見つけるために使用されています。これは、配列を5要素の塊に分割し、各塊のソートが一定であると主張します。サイズは固定されているためです。