당신의 표기법에는 문제가 있습니다. 일반 기관은 다음과 같아야합니다.
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)
.