알고리즘 #1 - 정렬 문제 #6 - Lower bounds #1

출처: https://www.whatwant.com

 

[ 공부 순서 ]

① Comparison sorts

② Lower bounds for (comparison) sorting

③ Decision-tree model

 

 

지금까지 공부한 Sorting 방식은 전부 비교(comparison)라는 행위를 이용하고 있다.

그런데, 이러한 Comparison sorting에 있어서 worst-case인 경우

최소한 "n log n" 번 비교를 해야한다는 것에 대한 증명 과정을 살펴보고자 한다.

 

 

① Comparison sorts

  - 정렬(Sorting)을 하기 위해서 크기 비교(comparison)만을 수행하는 알고리즘

  - 종류 : Insertion / Merge / Selection / Heap / Quick

 

② Lower bounds for (comparison) sorting

  - 모든 comparison sort는 worst case 상황에서 최소한  Ω(n log n) 번의 비교를 요구한다.

  → 이후 내용은 본 명제를 증명하는 과정

 

③ Decision-tree model

  - 모든 입력은 동일한 값이 없다고 가정

  - 비교(comparison)는 ＜, ＞, ≤, ≥ 4종류가 있지만, ai ≤ aj 하나로 모두 처리 가능

    ( ai ≤ aj 비교를 수행하게 되면 True or False 결과. 그러므로  ai ≤ aj 한 번만 수행하면 됨)

 

  - comparison sort는 decision-tree로 표현(설명) 가능

    . full binary tree

    . leaf는 입력 값들의 순열(permutation)

    . internal node는 어떤 값을 비교하는 지를 표현

 

  - 입력값 크기가 3인 insertion sort는 다음과 같은 decision-tree model로 표현

 

출처: https://www.whatwant.com

 

  - 예시를 하나 돌려보면 다음과 같다.

 

출처: https://www.whatwant.com

 

  - leaf 개수는 어떻게 계산할 수 있을까?

    . 입력값의 개수가 n 일 때, n!

    . 위 예시의 경우, n = 3 이기 때문에 3! = 6

 

  - Left / Right subtrees

    . 특정 node를 기준으로 왼쪽은 ai ≤ aj 값들만 존재, 오른쪽은 ai ＞ aj 값들만 존재

    . 밑의 node들도 모두 동일한 결과

 

출처: https://www.whatwant.com

 

  ★ the worst-case number of comparisons = the height of its decision-tree

    - h : height

    - n : number of element

    - n! : number of leaves

 

출처: https://www.whatwant.com

 

 

음.... 일단 내용은 파악했는데,

그래서 어쩌라고? ^^

 

다음에 살펴볼 counting 방식의 정렬(sorting)은 이와 다르다 !!!