DP Time complexity 분석 관련

  • kwangswei
    kwangswei

    아래 코드의 시간 복잡도는 O(N^3) 인가요? O(N^4) 인가요?

    class RepeatStringEasy {
    public:
        vector<vector<vector<int>>> cache;
        int _maximal(int l, int m, int r);
        int maximalLength(string);
        string s;
    };
    
    int RepeatStringEasy::_maximal(int l, int m, int r) {
        if (l >= m)
            return 0;
        if (l == s.size() || r == s.size())
            return 0;
    
        if (cache[l][m][r] >= 0)
            return cache[l][m][r];
    
        int& result = cache[l][m][r];
        if (s[l] == s[r]) {
            result = _maximal(l+1, m, r+1) + 2;
            return result;
        }
        result = max(_maximal(l+1, m, r), _maximal(l, m, r+1));
        return result;
    }
    
    int RepeatStringEasy::maximalLength(string s) {
        cache = vector<vector<vector<int>>>(50, vector<vector<int>>(50, vector<int>(50, -1)));
        int ret = 0;
        for (int i = 0; i < s.size(); ++i)
            ret = max(ret, _maximal(0, i, i));
        return ret;
    }
    

    저는 저 DP 테이블을 채우는 연산을 dominant term 이라 봐서 O(N^3) 인 것 같은데 (실제 구현을 iterative 하게 바꾸면 3중 for loop 로 구현할 수도 있고요.) 보이기에는 n^3 테이블을 채우는 함수를 바깥 for loop 에서 한 번 더 부르고 있으니 O(N^4) 같아 보이기도 합니다. 어떤게 맞을까요?


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

    cache 공간의 크기가 O(N^3)이고, 한 state를 채우는데 시간복잡도가 O(1)이므로 O(N^3)입니다.


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