3알고리즘 분석

 

이 알고리즘의 계산 복잡도를 분석해 봅시다. 같은 이름을 찾는 알고리즘이므로 두 이름이 같은지 ‘비교’하는 횟수를 따져 보면 됩니다.

먼저 n = 4일 때 비교 횟수를 볼까요?

 

위치	이름	비교 횟수	비교 대상
0	Tom	3	Jerry, Mike, Tom
1	Jerry	2	Mike, Tom
2	Mike	1	Tom
3	Tom	0	비교 안 함
전체 비교 횟수 = 3 + 2 + 1+ 0 = 6

표 3-2 n = 4일 때 비교 횟수

 

이제 일반적인 입력 크기인 n에 대해서 볼까요?

 

• 0번 위치 이름: n-1번 비교(자기를 제외한 모든 이름과 비교)

• 1번 위치 이름: n-2번 비교

• 2번 위치 이름: n-3번 비교

…

• n-2번 위치 이름: 1번 비교

• n-1번 위치 이름: 0번 비교

 

결국, 전체 비교 횟수는 0+ 1+ 2 + 3 + 4 + … + (n-1)번, 즉 1부터 n-1까지 의 합입니다.