私は次のような漸化式を持っています：
T（n）= 2T（n / 2）+ log 2 n
これを解決するために再帰ツリーメソッドを使用しています。そして最後に、私は次の方程式を思いついた：
T（n）=（2log 2 n）（n-1）-（1 * 2 + 2 * 2 2 + ... + k * 2 k ）ここで、k = log2nです。
この方程式のシータ表記を見つけようとしています。しかし、合計の閉じた式が見つかりません（1 * 2 + 2 * 2 2 + ... + k * 2 k）。T（n）の大きなシータ表記を見つけるにはどうすればよいですか？微積分を知っていれば、それを簡単に解くことができるはずです。
1 + x + x ^ 2 + ... + x ^（n + 1）=（x ^（n + 2）-1）/（x-1）
xを掛ける、x + x ^ 2 + x ^ 3 + ... + x ^（n + 2）=（x ^（n + 3）-x）/（x-1）
LHSを微分すると、x = 2のシリーズが得られます。RHSを微分すると、閉じた形が得られます。
You should use the Master Theorem to compute your complexity, it will be much easier.
私の計算によると、あなたはいくつかの間違いをしていると思います：
T（n）=（k-1）* log（n /（2 ^（k-1）））+ 2 ^ k * T（n / 2 ^ k）。
k = log（n）を入れてください
必要に応じて、ソリューションの画像を投稿できます。:)
これらの再発は、マスター定理で解決できます。あなたの場合a = 2、b = 2したがってc = logb(a) = 1。
あなたf(n) = log nとあなたn^cよりも速く成長するのでf、それは解決策を支配し、あなたは最初のケースに陥ります。したがって、複雑さはO(n)です。