조화수 (1) 썸네일형 리스트형 확률 퀵 정렬 분석 (Analysis on Randomized Quick-Sort) 요즘 백준 온라인 저지에서 문제를 하나씩 풀고 있습니다. 재밌더군요. 좀더 어릴 때부터 이를 해왔다면 더 좋지 않았을까 생각합니다. 주위에 문제 해결 분야를 열심히 연습하는 친구들이 많이 있는데, 그 친구들이 생각하는 건 확실히 남다른 것 같더라고요. 저도 그런 실력을 갖췄다면 어땠을까 생각하며 부러워하기도 합니다. 여튼 지금부터라도 한다면 도움이 되지 않을까요? 아무튼 백준 문제를 풀다 보니 정렬 알고리즘을 사용해야할 때가 자주 있었습니다. 그리고 그때마다 저 나름대로 퀵 정렬(quick-sort)을 구현해왔습니다.(의 std::sort()가 그렇게 좋다는 사실은 최근에야 알게 되었습니다. 지금은 직접 안 짭니다. 하하.) 그러다 문득 퀵 정렬의 시간 복잡도 분석이 궁금해졌습니다. 대학생 때 퀵 정렬이.. 이전 1 다음
