Quantize 시간 복잡도 계산? ( 종만북1 pg 250 부분)

  • 아기상어
    아기상어

    문제 풀이 방식과 논리는 이해가 되는데, 시간 복잡도 계산이 이해가 안 되서요.
    교재에 나와있는 코드의 시간복잡도가
    부분 문제의 수 "O(ns)"에다, 각 부분 문제의 답을 계산하는데 드는 시간 "O(n)"을 곱한 "O(n^2S)"입니다.

    여기서 부분 문제의 수가 왜 O(nS)가 되는 것인가요? ㅠㅠ
    아래에 작성한 코드 있습니다.

    //arr배열의 start인덱스에서 시작하는 크기 size의 수열에서 최소 오차 합 
int MinError(int start, int size)
{
    //부분 합
    //인덱스 오류 주의!
    int part;
    int part_z;

    if (start == 0)
    {
        part = partsum[start + size - 1];
        part_z = partsum_z[start + size - 1];
    }
    else
    {
        part= partsum[start + size - 1] - partsum[start - 1];
        part_z = partsum_z[start + size - 1] - partsum_z[start - 1];
    }


    int m = (int)(0.5 + (double)part / size);

    int result= part_z - 2 * m*part + m * m*size;

    return result;
}

int quantize(int start, int part)
{
    //양자화를 다 한 경우
    if (start == n)
        return 0;
    //숫자가 남았는데 더 이상 그룹을 지을 수 없는 경우
    if (part == 0)
        return MAX;
    if (cache[start][part] != 0)
        return cache[start][part];

    int *x = &cache[start][part];

    *x = MAX;

    for (int partsize = 1; start + partsize <= n; partsize++)
    {
        *x = min(*x, MinError(start, partsize) + quantize(start + partsize, part - 1));
    }

    return *x;
}

    5년 전
1개의 댓글이 있습니다.
  • Corea
    Corea

    quantize 함수가 같은 start와 part에 대해 단 한 번만 계산하게 되므로 (cache 를 사용했으니까요.) 부분 문제의 수가 O(nS) 이고, 그 안에서 for loop 부분이 O(n) 이기 때문에 최종적으로 O(n^2 S) 가 됩니다.


    5년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.