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;
    }
    

    7달 전
1개의 댓글이 있습니다.
  • Corea
    Corea

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


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