글 읽기 - 혹시 이게 O(nlogn) 이 아닌건가요? (분할 정복 사용)

didwngus01 3년 전 0

시간 복잡도가 O(nlogn)이라고 생각되는데, 채점에서는 시간 초과가 뜨네요. 어떤 부분이 잘못된 것인지 잘 모르겠습니다.

#include <iostream>

int heights[100000];

int findValley(int left, int right) {
    int min=1000000001, minIndex=0;
    for(int i=left ; i<=right ; i++) {
        if(heights[i]<min) {
            min = heights[i]; minIndex=i;
        }
    }
    return minIndex;
}

long long divide_conquer(int leftLimit, int rightLimit) {
    if(leftLimit==rightLimit) return (long long)heights[leftLimit];

    int valley = findValley(leftLimit, rightLimit);

    long long leftHalf=-1, rightHalf=-1;    //MIN value

    if(valley>leftLimit) leftHalf = divide_conquer(leftLimit, valley-1);
    if(valley<rightLimit) rightHalf = divide_conquer(valley+1, rightLimit);

    long long base = (long long)(rightLimit-leftLimit+1)*heights[valley];

    return std::max(std::max(leftHalf, rightHalf), base);
}


int main() {
    while(true) {
        int n;
        std::cin >> n;
        if(n==0) break;

        for(int i=0 ; i<n ; i++) {
            std::cin >> heights[i];
        }
        std::cout << divide_conquer(0, n-1) << "\n";
    }
}

퀵소트의 최악의 시간 복잡도가 O(n^2)인 것과 같은 원리로 이 코드도 최악의 경우에는 O(n^2)이 됩니다. 최악의 경우에 해당하는 것으로는 높이가 일정하거나, 오름차순, 혹은 내림차순으로 주어지는 경우가 있습니다. 이런 경우 범위가 k인 구간이 1과 k-1로 나누어지는 것이 반복되기 때문에 n, n-1, n-2, n-3, ... 1의 구간들을 처리하는 시간을 다 더하면 O(n^2)이 됩니다.

didwngus01 3년 전 0

평균은 O(nlogn)이지만 최악의 경우에 O(n^2)가 나오는 것이었군요. 이해됐습니다!!

빠른 답변 정말 감사합니다.

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

문제

문제

출처

ICPC

혹시 이게 O(nlogn) 이 아닌건가요? (분할 정복 사용)

didwngus01 3년 전 0

djm03178 3년 전 2

didwngus01 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말