4알고리즘 분석
이 문제의 알고리즘 효율성을 ‘저울질 횟수’를 기준으로 생각해 보겠습니다.
0번 동전과 나머지 동전을 일일이 비교하는 방법인 프로그램 17-1은 저울질이 최대 n-1번 필요합니다. 즉, 계산 복잡도가 O(n)입니다.*
동전 n개를 절반씩 나누어 후보를 좁히며 비교하는 방법인 프로그램 17-2는 계산 복잡도가 O(logn)입니다.**
셋째 마당 탐색과 정렬에서 배운 내용을 잘 기억하는 독자라면 순차 탐색과 이분 탐색이 떠올랐을 것입니다. 탐색 문제를 풀 때 문제 7의 순차 탐색에서는 하나씩 비교하여 값을 찾아내므로 계산 복잡도가 O(n)였습니다. 문제 12의 이분 탐색에서는 리스트가 이미 정렬되어 있다는 것을 전제로, 중간 값을 비교한 후 값이 있을 가능성이 없는 절반을 제외해 나가면서 값을 찾아내므로 계산 복잡도가 O(logn)이었습니다.
리스트 탐색 문제와 가짜 동전 문제는 겉으로 볼 때는 전혀 다른 문제로 보이지만, 잘 생각해 보면 구조가 비슷한 문제라는 것을 알 수 있습니다.
* 사실 마지막 동전은 저울에 올려보지 않아도 알 수 있기 때문에 n - 2번 저울질로도 가짜 동전을 찾아낼 수 있습니다(계산 복잡도는 O(n)으로 같습니다).
** 만약 주어진 동전을 세 그룹으로 나누면 O(log3n)으로도 가짜 동전을 찾을 수 있습니다(이 계산 복잡도는 O(logn)과 같습니다).