私は宿題の質問に取り組んでいました。私にはnlognと以下の繰り返しを比較する必要があります。 nlognが下か、上か、または以下の時間複雑度によって制限されているかのように。 再発関係の解法複雑さ？
| 5 n = 1
--| 2T(n/2) + n n > 1
でハンズオンを取得することができます：
2T(n/2) + n
2[2T(n/4) + n/2] + n
2^2*T(n/2^2) + 2n
you find the pattern if you keep on substituting new n
2^k*T(n/(2^k)) + kn
at this point you solve for closed form using the base case then n = 1
so for n/n = 1, we set 2^k = n, so k = logn
sub in k
2^(logn) * T(1) + (logn) * n
note that 2^logn = n with base 2 and T(1) = 5 for the base case
so we obtain 5n + nlogn
5n + nlogn is just O(nlogn)
我々はO（nlogn）としての両方を持っているので、それがタイトバウンドでありますまたは大きなシータ。
また、マスター定理を使用して複雑さを簡単に差し引くこともできます。あなたがそれを学んだ場合。 Θ（nlogn）で満たすケース2、上記
a = 2
b = 2
c = 1
あなたがしたことを理解させてください。どうも – bychit
短答 - この再発のO表記を見つけるには、「マスター定理」を使用することができます（また、使用する必要があります）。
マスター定理は、再発を解決するための便利なツールであり、結果をすぐに得ることができるので、最初のオプションにする必要があります。あなたは（私はこの権利をやった願っています）再発を解決するために、このexercise
をWikiへ参照してください。あなたは再帰木を試みたことがありますか？ – synchronizer
あまりよくありません。私の本は、離散数学 – bychit
再帰ツリーとの証拠の多くを持っているだけでなく、結果を与える必要があります。これは一般的で簡単な見直しの再発であるので、あなたは非常に簡単に結果を見つけることができます –