RSS구독하기:SUBSCRIBE TO RSS FEED
즐겨찾기추가:ADD FAVORITE
글쓰기:POST
관리자:ADMINISTRATOR

O(n) 선택 알고리즘에서 집단을 3개로 나누면?


5개로 나눌 O 성능 분석

Blum, Floyd, Pratt, Rivest, & Tarjan(1973) 선택 알고리즘(정확히는 median-of-medians) O(n) 성능으로 순위 통계량(i번째 원소) 검색할 있게 해준다. 알고리즘은 n개의 원소를 1) 5개의 집단으로 나누고 집단의 중간값(median) 찾아(Θ(n)) 2) 재귀적으로 n/5 집단의 중간값을 찾는 Select 호출한다(T(n/5)). 3) 중간값을 피봇(pivot) x 삼고, 원소를 분할(partitioning)한다(Θ(n)). 4) 최악의 경우 x보다 (작은) 원소가 5/2·└└n/5/2 = 3n/10 n/4개 있으므로(n50) n - n/4 = 3n/4개에 대해 재귀호출을 하게 된다(T(3n/4)). 이상에서 T(n) = T(n/5) + T(3n/4) + Θ(n)이고, 강의노트를 참고해 점화식을 풀면 O(n) 된다. 그런데 이때 집단을 5개가 아니라 3개로 나누면 어떻게 될까? 여전히 O(n)일까?

 

3개로 나눌 O 성능 분석

위의 1)에서 3개의 집단으로 나누고(Θ(n)) 2)에서 n/3 집단의 중간값을 찾으며(T(n/3)) 3) 동일하다(Θ(n)). 4)에서 최악의 경우 x보다 (작은) 원소 3/2·└└n/3/2 = 2n/6 개에 대해 재귀호출을 한다. 이때의 성능이O(n)이라고 가정하고 추측확인법(guess & verify) 적용해보자. n6일 때 2n/6 n/6이므로, T(n) = T(n/3) + T(5n/6) + Θ(n) 1/3cn + 5/6cn + Θ(n) = 7/6cn + Θ(n) > cn 되어 가정이 틀렸음을 있다. , 3개의 집단으로 나누면 Select 알고리즘의 특성인 선형 성능을 잃는다는 결론을 얻는다.

여기서 만약 O(n2)으로 가정하면 T(n) = 1/9cn2 + 25/36cn2 + Θ(n) = 29/36cn2 + Θ(n) < cn2으로 가정을 만족한다. 근접한 상계를 찾기 위해 이번엔 O(n·lg n)이라 가정하면 T(n) = cn/3(lg cn – lg 3) + 5cn/6(lg cn + lg5 – lg 6) + Θ(n) = 7cn/6(lg cn) – cn/6(2lg3 - 5lg5 + 5lg6) + Θ(n) = 7/6cn(lg cn) + cn/6(lg9 – lg25 + lg7776) + Θ(n) > 7/6cn(lg cn) + Θ(n) > cn(lg cn)이므로 가정에 모순이다.

따라서 1<k2 O(nk) 만족한다고 가정한다. 그리고 k 1.1에서 0.1 높이며 대입해 나가면 1.4(소수점 자리를 늘리면 1.3725 정도)에서 최초로 가정이 만족되므로 O(n1.4) 찾게 된다.

2007/08/03 13:43 2007/08/03 13:43
이 글에는 트랙백을 보낼 수 없습니다
와우  | 2014/10/09 00:57
깔끔하게 풀어두셔서 많은 도움이 되었습니다 ^^

감사합니다.
웅쓰:웅자의 상상플러스
웅자의 상상플러스
전체 (379)
게임 (5)
영화 (2)
기타 (23)
맛집 (5)
영어 (2)
대수학 (3)
형태소 (5)
Hacking (9)
Linux (112)
HTML (48)
Application_developing (48)
Web_developing (102)
Window (11)
«   2018/11   »
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  
  1. 2016/01 (1)
  2. 2015/12 (3)
  3. 2015/10 (3)
  4. 2015/03 (2)
  5. 2015/01 (4)