빅오메가1 2022 서울시 자료구조(A) 해설 9~11번 정답) 1 이 문제는 내가 푼 방식이 맞는지 모르겠지만 한번 끄적여본다. T(n) = 2T(n/2) + n에서 T(n/2) = 2T(n/4) + n/2를 대입해주면, T(n) = 2(2T(n/4) + n/2) + n = 2^2 T(n/4) + 2n이 된다. 여기서 T(n/4) = 2T(n/8) + n/4를 대입해보면 T(n) = 2^3T(n/2^3) + 3n이 된다. 이를 통해서 T(n)을 T(n) = 2^k T(n/2^k) + kn로 일반화시킬 수 있다. 여기서 T(n)이라는 식을 가만히 살펴보면, T(n/2)가 실행되며 결국 T(0) = T(1) = 1이라는 조건을 사용할 때까지 실행된다. 그렇다면 우리가 일반화한 T(n/2^k)가 T(0) 또는 T(1)이 되어야 한다는 것이다. 그렇다면 k를 n으로.. 2022. 12. 17. 이전 1 다음
