私はこれにかなり新しいです私の分割プログラム、プログラムの実行時間を処理していますか？
void splitX(int x) {
if (x<=1) {return x;};
splitX(n/2);
System.out.println("splitting in progress");
splitX(n/2);
splitX(n/2);
splitX(n/2);
}
の運転時間を仕事にしようとしています、これはこれまでにやっていることです。
T(n) = 4T(n/2)
= 4^2T(n/2^2)
= 4^3T(n/2^3)
= 4^kT(n/2^k)
= O(log n)
私は、正しい軌道に乗っアムイムは少し混乱してき、また、あなたは、印刷ラインを考慮しなければならないのですか？
analyzisが終了するまで、溶液を4^kT(n/2^k) != O(log n)4^k以降は一定ではないことT(n) = O(n^2)
注真です。
はanalyzisを見てください：
T(n) = 4T(n/2) =
= 4^2T(n/2^2)
= 4^3T(n/2^3)
= 4^kT(n/2^k)
= 4^log(n)*T(1) =
= 4^log(n) * 1 =
= (2^log(n))^2 =
= n^2
= O(n^2)
正式にそれを証明するために：私たちはinduction
基本使用：T(1) = 1 = 1^2
を各k <= n T(2n) = 4*T(n) =(induction hypothesis) 4*n^2 = (2n)^2
ためT(n) = n^2を想定したがって、帰納法の仮定が真であるとT(n) = n^2
ヨーUは、（N/2）+ cは
は今= 4、Bを使用してマスターtheorumを適用形態の4T
T（N）=であるwolfram alpha
私は、あなたの再帰関数へのlog（N）呼び出しを行います。これを定数で掛けても複雑さは変わらないし、印刷ラインも（すべての宿題に関連して）必要はない。
発現に対するこの結果を確認することができ= 2かつf（n）= c;
T（N）= O（N^loga）//ベース2
T（N）= N^2
これに感謝します。正面の4人がどのように違いを生み出すか説明できますか？例えば3に変更すると、実行時間を変更できますか？ – Lunar
@月：はい。 「正面の4」は数式を「力の」ものにします。あなたの解析には '4 * 4 * ... * 4' [logn times]につながる' T（n）= 4^k * T（n/2^k） 'mがあります。それが "3"であれば、 '3 * 3 * ... * 3' [logn times]となり、' 3^logn' [より大きく、 'n^2]より小さくなります。 ] – amit