Merge Sort 의 Complexity 는 잘 알려진대로 n log(n) 입니다.. 그럼 Merge Sort를 할때, 2개로 나누는걸 3개로 나누는걸로 바꾸면 복잡도는 얼마가 되나요? 당연히 n log_3(n) (밑이 3인 로그)일줄 알았는데,생각해보니 이렇게 간단히 나올리가 없더군요.. 고수님들의 답변 기다립니다 ㅠㅠ
3개의 덩어리가 각각 이미 정렬된 상태라고 하면, 2개 골라서 우선 합병하고, 나머지 하나 합병하면 되지 않을까요? 만약 n, m, k개의 원소를 갖는 3덩어리라면 최악의 경우에, 일단 n+m-1번 비교를 하고 다시 (n+m-1)+k-1번 비교를 하겠죠. 전체 비교횟수는 2n+2m+k-2가 되네요. 그럼 n=m=k라고 가정하면 5n-2회 비교합니다.
따라서 T(n) = 3T(n/3)+5(n/3)-1
이제 이 점화식을 풀면...
졸립니다.
-------------------------- 피할 수 있을때 즐겨라!http://snowall.tistory.com
피할 수 있을때 즐겨라! http://melotopia.net/b
점화식을 다 풀기 귀찮으시다면, 대신 master theorem을 이용하여 big-O (log_3 n * n) = big-O ( n log n )으로 둘로 나눌 경우와 같게 나옵니다
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
3개의 덩어리가 각각
3개의 덩어리가 각각 이미 정렬된 상태라고 하면, 2개 골라서 우선 합병하고, 나머지 하나 합병하면 되지 않을까요?
만약 n, m, k개의 원소를 갖는 3덩어리라면
최악의 경우에, 일단 n+m-1번 비교를 하고 다시 (n+m-1)+k-1번 비교를 하겠죠. 전체 비교횟수는 2n+2m+k-2가 되네요.
그럼 n=m=k라고 가정하면 5n-2회 비교합니다.
따라서
T(n) = 3T(n/3)+5(n/3)-1
이제 이 점화식을 풀면...
졸립니다.
--------------------------
피할 수 있을때 즐겨라!
http://snowall.tistory.com
피할 수 있을때 즐겨라! http://melotopia.net/b
점화식을 다 풀기
점화식을 다 풀기 귀찮으시다면, 대신 master theorem을 이용하여
big-O (log_3 n * n) = big-O ( n log n )으로 둘로 나눌 경우와 같게 나옵니다
댓글 달기