글 읽기 - Approximate Median 을 pivot 으로 잡는데 시간초과를 받았습니다

zxcvber 5년 전 0

약 93% 쯤에서 시간초과를 받는 것 같습니다.

O(n) 인건 맞는것 같은데 상수가 지나치게 큰 걸까요?

함수호출의 오버헤드인지...

피봇으로 잡은 x를 배열에서 찾는게 오래걸리는 것인지...

잘 모르겠습니다!

도와주세요! 감사합니다!

// kth smallest element in O(n) time
// Using median of medians as pivot

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int arr[5050505];

// finding median in a small array
int median(int arr[], int n) {
    sort(arr, arr + n);
    return arr[n / 2];
}

// partition arr[st ... ed] with x as pivot
int partition(int arr[], int st, int ed, int x) {
    int i, tmp;
    // search for x in arr, and move it to the end
    for(i = st; i < ed; ++i) {
        if(arr[i] == x) break;
    }
    tmp = arr[ed];
    arr[ed] = arr[i];
    arr[i] = tmp;

    // Partition
    i = st - 1;
    for(int j = st; j < ed; ++j) {
        if(arr[j] <= x) {
            // increment i then swap arr[i] and arr[j]
            tmp = arr[j];
            arr[j] = arr[++i];
            arr[i] = tmp;
        }
    }
    tmp = arr[++i];
    arr[i] = arr[ed];
    arr[ed] = tmp;
    return i;
}

// kth smallest element from arr[st ... ed]
int kth(int arr[], int st, int ed, int k) {
    int n = ed - st + 1;
    int i, med[(n + 4) / 5]; // divide into ceil(n / 5) groups
    for(i = 0; i < n / 5; ++i) {
        med[i] = median(arr + st + 5 * i, 5);
    }
    if(5 * i < n) { // last group
        med[i] = median(arr + st + 5 * i, n % 5);
        ++i;
    }
    // choose median of medians
    int medOfMed = (i == 1) ? med[i - 1] : kth(med, 0, i - 1, i / 2);
    int pivot = partition(arr, st, ed, medOfMed);
    int idx = pivot - st + 1;
    // found
    if(idx == k) return arr[pivot];
    // search left
    else if(idx > k) return kth(arr, st, pivot - 1, k);
    // search right
    else return kth(arr, pivot + 1, ed, k - idx);
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; ++i) scanf("%d", arr + i);
    printf("%d", kth(arr, 0, n - 1, k));
    return 0;
}

doju 5년 전 2

배열이 전부 같은 값으로 이루어져 있을 때 partition이 굉장히 나쁘게 됩니다. Wikipedia의 의사코드를 참조해 보면 이런 상황을 대비하는 부분이 있는데, 코드를 잘 읽어 보세요.

zxcvber 5년 전 0

전부 같은 값일 경우 정말 그렇게 되겠군요, 미처 생각하지 못했습니다! 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Approximate Median 을 pivot 으로 잡는데 시간초과를 받았습니다

zxcvber 5년 전 0

doju 5년 전 2

zxcvber 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말