positivesmile
50
2018-10-13 20:23:10
3
717

알고리즘 관련 질문드립니다.


질문 : "최악의 경우 선형시간 선택 알고리즘" 이라는 이름의 알고리즘이 다른 이름의 알고리즘으로 존재하는지 아시는분 계신가요?


' 최악의 경우 선형시간 선택 알고리즘 ' 

  └>  평균 선형 시간 선택 알고리즘의 시간이 O(n^2) 이 소요되는 것을 의미합니다.

' 평균 선형 시간 선택 알고리즘 '

 └> 배열에 주어진 값을 퀵 정렬처럼 분할한 후 재귀호출 방법을 쓰게되면, 평균적으로 선형 시간에 i번째 작은 원소를 찾을 수 있는 알고리즘 입니다 .


정확한 코드가 아닌 책에 나온 의사코드는 다음과 같습니다.

구현해야 하는 알고리즘은 linearSelect(A,p,r,i) 라는 알고리즘인데요

저 제목으로 구글링을 해봐도, 구현된 알고리즘이 전혀 없는것 같아서요!

혹시나 다른 이름으로 이러한 의사코드를 가진 알고리즘이 존재하는지 아시는분 계신가요?

정보가 많이 빈약하지만,, 아시는 개발자님들께서는 댓글 부탁드리겠습니다!


select(A,p,r,i) //  배열 A[p ~ r]에서 i번째 작은 원소를 찾는다.
{
     if(p=r) // 원소가 하나뿐인 경우 , i는 반드시 1
        return A[p];
     q = partition(A,p,r); // 
     k = q-p+1; // k는 기준원소가 전체에서 k번째 작은 원소 이라는 것을 의미
     if(i<k)  // 왼쪽 그룹으로 범위를 좁힌다.
       return select(A,p,q-1,i);
     else if (i=k)  // 기준원소가 바로 찾는 원소이다.
       return A[q];
     else // 오른쪽 그룹으로 범위를 좁힌다. 
       return select(A, q+1, r, i-k);
}

partition(A[], p,r)
{
    x = A[r]; // 기준원소
    i = p-1; // i는 1구역의 끝지점
    for (j=p; j<r-1; j++) // j는 3구역의 시작지점
    {
        if(A[i] <= x )
        {
           A[++i] ↔ A[j]; // i값 증가 후 A[i] 값과 A[j]값을 교환
        }
        A[i+1] ↔ A[r]; // 기준 원소와 2구역 첫 원소 교환
    return i+1;
}
linearSelect(A,p,r,i)

1. 원소의 총 개수가 5개 이하이면 i번째 원소를 찾고 알고리즘을 끝낸다.
2. 전체 원소를 5개씩의 원소를 가진 n/5개의 그룹으로 나눈다.
3. 각 그룹에서 중앙값을 찾는다. (if 원소가 5개이면 3번째 원소를 찾는다)
   이렇게 찾은 중앙값들을 m1, m2 등이라 한다.
4. m1, m2 들의 중앙값 M을 재귀적으로 구한다.
   원소의 총수가 홀수이면 중앙값이 하나이므로 문제가 없고 원소의 총수가 짝수이면, 두 중앙값 중 임의로 선택한다.
5. M을 기준원소로 삼아 전체 원소를 분할한다.
6. 분할된 두 그룹 중 적합한 쪽을 선택하여 1 ~ 6을 재귀적으로 반복한다. 
0
0
  • 답변 3

  • puRple
    30
    2018-10-14 00:14:39

    Partition 쓰는 거 보고 Quick sort 찾았어요 요즘 제가 알고리즘 정렬쪽 보느라...


    퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다

    https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC



    1
  • yeori
    589
    2018-10-14 09:43:39

    함수 이름 linear selection 이 말씀하시는 그겁니다.


    최악의 경우 선형시간 선택 알고리즘이라는 말이 좀 이상한데 풀어쓰면 "대체로 선형 시간이 걸리는데 재수없으면 O(n^2)이 걸릴 수 있는 알고리즘"이라는 뜻입니다.

    여기서 말하는 "재수없으면"이라는 뜻은 위 코드에서 주석으로 "기준원소"라고 쓰인 x가 배열에서 가장 작거나 가장 큰 값이 계속 걸리는 경우 파티셔닝의 효과를 전혀 보지 못한다는걸 말합니다.

    그래서 재수없으면 들쭉날쭉 할 수 있는 알고리즘을 개선하기 위해서 N/5개의 집합으로 쪼개서 각 잡합을 정렬한 후 중간값 median 을 구하고, 이 중간값들을 정렬해서 다서 중간값을 구해서 이 놈을 pivot(기준원소)으로 선정하면 "재수없는 경우"를 피할 수 있다, 뭐 이런 뜻입니다.

    이러다보니 구현이 더럽고 복잡해지죠.

    1
  • positivesmile
    50
    2019-01-18 23:32:29

    답변 감사합니다. 저때는 몰랐지만 계속해서 공부를 하다보니 어느정도 깨달았는데, 한번 더 읽어보니 생각이 다시나네요 감사합니다^


    0
  • 로그인을 하시면 답변을 등록할 수 있습니다.