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까지 의 합입니다.

    신간 소식 구독하기
    뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.