언어 자료구조 알고리즘/디딤돌 알고리즘 (C언어)

[C언어 알고리즘] 4.3.1 병합 정렬 알고리즘 성능 분석

언제나휴일 2016. 12. 1. 01:22
반응형

[C언어 알고리즘] 4.3.1 병합 정렬 알고리즘 성능 분석


병합 정렬 알고리즘 성능을 분석해 보아요.

병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    ah:= n/2

    bh:= n - ah;

    조건(n 1보다 작거나 같으면) 종료

    병합정렬(base,ah,compare)

    병합접열(base+ah,bh,compare)

    tbase에 동적 메모리 할당(원소크기*원소개수)

    메모리 복사(tbase,base)

    ai:=0

    bi:=ah

    i:=0

    반복(ai ah보다 작으면서 bi n보다 작다)

        조건(tbase[ai] tbase[bi]보다 작거나 같으면

            base[i] := base[ai]

            ai:= ai+1

        아니면

             base[i]:= base[bi]

             bi:= bi+1

        i:=i+1

    반복(ai ah보다 작다)

        base[i]:= tbase[ai]

        i:=i+1

        ai:=ai+1

    반복(bi n보다 작다)

        base[i]:= tbase[bi]

        i:=i+1

        bi:=bi+1

 

병합 정렬은 배열의 원소가 1개일 때까지 분할하죠.

분할한 두 개의 배열을 하나로 합치기 위해서는 두 배열의 원소 개수만큼 비교해요.

원래 배열을 분할한 배열을 합치기 위해 비교는 n번 수행하겠죠.

결국 분할 횟수 * n 만큼 수행해요.

분할은 원속 개수를 n=>n/2=>n/4... 형태로 분할하므로 2 h 승이 1이 될 때까지 분할하죠.

수행 속도는 h*n 이예요.

2 h 승이 n이므로 h logn예요.

따라서 수행 속도는 O(nlogn)이라고 말할 수 있어요.

반응형