|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
08/10/18 16:24
Time Complexity를 구하는 방법으로는 여러가지가 있습니다.
(1) substitution method : T(n)=2T(n/2)+c2n의 경우 T(n)의 Upper bound를 예측하고 그 값을 식에 넣어서 계산하는 방식입니다. (2) iteration method : T(n)=2T(n/2)+c2n 를 계속해서 풀어봅니다. T(n)=2(2T(n/4)+c2(n/2))+c2n T(n)=2(2(2T(n/8)+c2(n/4))+c2(n/2))+c2n ... 이렇게 해서 T(n) 부분이 상수의 복잡도를 가지는 k를 찾아내고 그 k값을 다른 부분에 대입해서 식을 풀어야 하는데 자세한 과정은 너무 복잡해서 생략합니다. (3) Master theorem : 위와 같은 일반적인 형태의 재귀적 함수에 적용될 수 있는 방법입니다. T(n)=AT(n/B)+c2n 의 경우에 logBA와 C의 값을 비교하여 logBA<C T(n)=n^logBA logBA=C T(n)=n^c*logn^(d+1) logBA>C T(n)=n^c*logn^d 입니다 c는 뒷쪽 항의 n의 지수이며, d는 뒤쪽 항의 로그n의 지수입니다 T(n)=2T(n/2)+c2n에서는 A=2,B=2,c=1,d=0이므로 logBA=1, c=1 두 값이 같은 경우이므로 T(n)=nlogn이 되겠네요. 자세한 내용은 알고리즘 책을 참고하시는게 좋을듯하네요-
08/10/18 16:32
맛스타 정리 어려우시면
T(n) = aT( n / b) + f(n) 에서 h(n) = n ^ logba 라할때, f(n)과 h(n)을 가지고 f(n) / h(n)에서 n을 무한대로 보낼 때 0이면, 즉 h(n)이 더 무거우면 T(n) = 세타(h(n)) 이구요. (h(n)이 수행시간 결정) f(n) / h(n)에서 n을 무한대로 보낼 때 무한대이면, 즉 f(n)이 더 무거우면, 충분히 큰 모든 n에 대해 af(n/b) < f(n)이면 T(n) = 세타(f(n)) 이구요. (f(n)이 수행시간 결정) f(n) / h(n)에서 n을 무한대로 보낼 때 1이면, T(n) = 세타( h(n)logn 이에요.
|
||||||||||