Improving selection

Selection of Both Maximum and Minimum Elements

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

struct Result {
    int minValue, maxValue;
};

struct Result MAXMIN(int A[], int l, int r)
{
    struct Result ret;
    if (l == r) {
        ret.minValue = ret.maxValue = A[l];
        return ret;
    }
    else if (r - l == 1) {
        ret.minValue = (A[l] < A[r] ? A[l] : A[r]);
        ret.maxValue = (A[l] > A[r] ? A[l] : A[r]);
        return ret;
    }

    struct Result ret1, ret2;
    int mid = (l + r) / 2;
    ret1 = MAXMIN(A, l, mid);
    ret2 = MAXMIN(A, mid + 1, r);

    ret.minValue = (ret1.minValue < ret2.minValue ? ret1.minValue : ret2.minValue);
    ret.maxValue = (ret1.maxValue > ret2.maxValue ? ret1.maxValue : ret2.maxValue);
    return ret;
}

int main()
{
    int A[10] = { 5,3,1,9,7,6,4,2,10,8 };

    printf("Elements : ");
    for (int i = 0; i < 10; i++) {
        printf("%d ", A[i]);
    }
    printf("\n\n");

    struct Result r = MAXMIN(A, 0, 9);
    printf("Max : %d, Min : %d\n", r.maxValue, r.minValue);

    return 0;
}

위 코드의 시간복잡도

---

시간복잡도 계산

---

Selection of the k-th Smallest Element

1. naive하게 k번째로 작은 값을 찾는다.

2. min-heap을 만들고 가장 작은 값 찾는 것을 k번 반복한다.

이걸 O(n)에 해결할 수 없을까?

T(n)=T(an)+T(bn)+cn (a+b<1)이라면 시간복잡도가 O(n)이 된다는 사실을 이용하자.

 

1단계 - S를 다섯개의 집합으로 나누자.

2단계 - 각각의 집합을 sort하자

3단계 - 각각의 집합의 가운데 값을 M이라고 할 때, M을 기준으로 sort하고 그 중앙을 m이라고 한다.

4단계 - S1을 m보다 작은 집합, S2를 m과 같은 집합, S3를 m보다 큰 집합이라고 하자.

만약 |S1|>=k 라면 k번째로 작은 수는 S1에서 찾으면 된다.

만약 |S1|+|S2|>=k 라면, m은 k번째로 작은 수가 된다.

그 외에는 (k-|S1|-|S2|)번째를 S3에서 찾으면 된다.

 

예를 들어서 n=1000000이고 k=9572일 때,

|S1|=27512라면, S1에서 k번째를 구하면 되고,

|S1|=9500,|S2|=85라면 m이 k번째가 되고,

|S1|=100, |S2|=35 라면 k-|S1|-|S2|번째가 답이 된다.

또 파란영역과 보라색 영역은 최소한 S영역의 1/4을 차지한다.

S1의 영역과 S2의 영역은 겹칠 수 없고, 각각의 최소크기가 S의 1/4이므로

|S1|<=3S/4, |S3|<=3S/4가 성립한다.

---

Master Theorem 1

---