프로그램
2007. 3. 22.
퀵정렬이 n log n이 되는 이유!
출처 네이버블로그 > 공부는 자신의 인생을 바꾸는 드라마다. http://blog.naver.com/newlogin_kr/140035838340 앞서 우스개 암기에서 보여드렸지만 퀵서비스맨의 앤은 자연을 사랑하는 앤이다. (n로브(그) n ) 라고 했습니다. 어떻게 된걸까요? 정공법으로 쳐 봅시다.(만만하다는 사실은 이미 앞서 설명드렸으니 자신감 무장하시고) 책에 단 두줄로 이렇게 모든것을 표현햇습니다. 정확히 둘로 나누는 경우가 모든 경우에 발생한다면 둘로 나누고 난 것들의 2배의 시간과 반복되는 횟수2(T(n/2))를 평균치 세타로 바꿔서 단지 n번만 반복하므로 세타(n)이 나온다. 다시 말해보면 일단 절반으로 자른다.그러면 2개의 배열이 생성됨 각각은 n/2 길이 처음 길이가 n이고 처리 식의 시간..