反復法によるt（n）= t（n/2） + 2^nの再帰的な複雑さを解くにはどうすればよいですか？

Question

上限と下限を見つけようとしています。これはおそらくO（2^n）です

n <= 4のt（n）= 1

私は一般器官が次のことを知っています：

t（n）= t（n/2^（i + 1）） + i = 0から2^（n/2^i）までの合計

---

ここから私は進む方法を知りません。

Answer 1

あなたの表記にはいくつかの問題があります。一般器官は次のとおりです。

T(n) = T(n/2^(i+1)) + sum from k=0 to i of 2^(n/2^k)

このステップの後、私たちは許可します i = log(2, n) - 1, 、 となることによって T(n/2^(i+1)) = T(1).

したがって、 T(n) = T(1) + sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k).

ご了承ください sum from k = 0 to (log(2, n) - 1) of 2^(n/2^k) は 2^n + 2^(n/2) + 2^(n/4) + ..., 、それよりも小さい 2^n + 2^(n-1) + 2^(n-2) + .... 。ただし、後者のものはそうです 2^(n+1) - 1. 。したがって、前者のものは間にあります 2^n と 2^(n+1). 。したがって、 和 は O(2^n).

それで T(n) = O(2^n).