반복 방법으로 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에서 k of 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).