3알고리즘 분석

 

문제 3에서 살펴본 동명이인을 찾는 알고리즘(프로그램 3-1)은 리스트 안에 들어 있는 모든 사람을 서로 한 번씩 비교하여 같은 이름이 있는지 찾아내는 방식이었습니다. 즉, 사람 수가 n일 때 계산 복잡도는 O(n²)이었습니다.

반면 딕셔너리를 이용해 동명이인을 찾는 알고리즘(프로그램 14-1)은 1단계로 리스트 정보를 한 번 읽어서 각 이름과 등장 횟수를 딕셔너리에 넣는 동작(n번 처리)을 하고, 2단계로 딕셔너리 안에 저장된 서로 다른 이름을 확인하여 등장 횟수가 2 이상인 자료를 찾습니다(n번 이하 처리). 이는 for 반복문을 겹쳐서 사용하지 않고 따로따로 두 번 반복하는 과정이므로 대문자 O 표기법으로 표현하면 O(n)에 해당합니다.

프로그램에서 for 반복문이 여러 번 나올 때는 서로 겹치느냐 겹치지 않느냐에 따라 계산 복잡도가 많이 달라집니다.

 

위치	for 반복문이 겹친 예	for 반복문이 겹치지 않은 예
코드	for i in range(0, n - 1):     for j in range(i + 1, n):         # 중첩된 반복 부분	for i in range(0, n):     # 반복 1: 이 부분은 n번 실행 for i in range(0, n):     # 반복 2: 이 부분은 n번 실행
실행 횟수	n(n - 1) / 2	2n
계산 복잡도	O(n2)	O(n)

표 14-2 for 반복문 중첩 여부에 따른 계산 복잡도 차이