| [ QuizWit ] in KIDS 글 쓴 이(By): guest (sol) <dor184130.kaist.> 날 짜 (Date): 2002년 1월 8일 화요일 오전 10시 54분 27초 제 목(Title): Re: 천칭 소팅문제 천칭을 사용하는 것이므로 당연히 천칭의 양쪽에 올려놓을 수 있는 구슬의 개수에는 제한이 없습니다. 그리고 천칭을 사용했을 때는 분명 천칭을 사용하지 않는 단순한 비교보다는 적은 횟수가 사용될 것입니다. 특수한 경우이긴 하지만 n개의 구슬 중에서 단 한개만 무게가 다른 경우 이러한 구슬을 찾아내기 위해 단순한 비교로 찾아 낸다고 했을 때 worst한 경우에는 최소 n/2번의 비교 횟수가 필요하지만 천칭을 사용했을 땐 구슬이 13개 일때 3번 40개일 때 4번 121개일 때 5번의 비교횟수가 필요하므로 단순한 비교보다는 훨씬 적은 횟수가 든다는 것을 알 수 있습니다. 제가 보기엔 거의 O(logn) 정도가 되는 거 같네요! 따라서 n개의 구슬이 전부 무게가 다른 경우에도 천칭을 이용했을 때 비교횟수에 있어서 많은 절약이 있을 거 같습니다. |