개요
이 포스팅에서는 PS를 하면서 독특했던 시간 복잡도에 대하여 정리한다.
$T(n)=T(a)+T(n-a)+O(\min(a,n-a))$
결론부터 말하면 위와 같은 구조의 시간 복잡도를 갖는 코드는 $O(n\log{n})$ 이다.
기본적으로 학부 과정에서 시간 복잡도를 분석하는 방법으로 Recursion Tree를 배웠을 것이다.
하지만 Recursion Tree를 그려도 merge sort와 달리 트리의 depth를 판단하는 것과, 각 depth별 시간을 찾는게 까다로울 것이다.
따라서 위와 동치인 문제로 환원을 하여 생각해 보도록 하자.
Disjoint Set을 효율적으로 구현하는 방법에는 다양한 방법이 있음을 알고리즘 수업등을 통해 알 것이다.
union by rank, union by size, path compression 등이 대표적으로 존재하며, 이것에 대한 설명은 생략하도록 한다.
위의 3가지 방법중 현재 상황과 정확히 일치하는 방법은 union by size이다.
Recursion Tree를 그려보면, 우리는 2개의 노드가 합쳐져서 결국 하나의 노드로 귀결됨을 쉽게 관찰 할 수 있다.
이때 2개의 노드가 합쳐지는 과정에서 걸리는 시간은 $O(min(a,b))$ ($a, b$는 각 노드의 크기) 가 되고, 이는 우리가 구하고자 하는 식의 상황과 일치한다. 즉, union by size와 시간 복잡도가 같음을 알 수 있다.
union by size가 $O(n\log{n})$ 임은 각 원소가 최대 합쳐지는 횟수가 $O(\log{n})$ 이란 사실로부터 구할 수 있다. 원소가 총 $n$개 존재하고, 한 원소는 최대 $O(\log{n})$ 번 합쳐지므로 자명히 전체 시간 복잡도는 $O(n\log{n})$ 이 된다. 이렇게 Naive한 연산을 하지만 연산 횟수의 상한선을 결정하여 시간 복잡도를 낮추는 아이디어는 다른 문제를 푸는 데 사용이 되기도 한다. 대표적인 방법으로 소위 small to large trick 이라 알려진 방법이 있고, union by size 는 해당 트릭을 Disjoint Set의 구현에 사용한 경우라 볼 수 있다.
사실 이러한 시간 복잡도를 접하는 경우가 흔하지 않다. (괴수들은 잘 모르겠다) 본인의 경우 위의 시간 복잡도를 아래 문제를 푸는 과정에서 처음 보았고 이 글을 읽는 사람들에게 추천 문제로 링크를 남겨놓겠다.
$\displaystyle T(n)=\sum_{k=1}^{|P|} {n \over p_k} (p_k는\ n이하\ 소수)$
위와 같은 시간 복잡도는 정수론 문제 등을 다룰 때 자주 등장하는 식이다. 이 역시 소수의 개수가 얼마인지 추측이 힘들기 때문에 정확한 값의 계산이 어려울 것이다. 하지만 위의 경우 시간 복잡도는 $T(n)=O(n\log{|P|})$ 이고, 이에 대한 증명을 아래에 적겠다.
Proof )
$\displaystyle T(n)=\sum_{k=1}^{|P|} {n \over p_k} \leq \displaystyle \sum_{k=1}^{|P|} {n \over k}=\displaystyle n\sum_{k=1}^{|P|} {1 \over k}$
$\displaystyle n\sum_{k=1}^{|P|} {1 \over k} \leq n \left(1+\int_{1}^{|P|} {1 \over x}\, dx \right)=n\left(1+\ln{|P|}\right)=O(n\log{|P|})$
위의 증명에서 적분식으로 넘어가는 과정은 그래프를 그려보면 쉽게 이해가 될 것이다. 특히나 중간에 나오는 시그마 식과 유사한 형태가 최근 코드포스에도 출제가 된 바가 있다. Naive한 시도라서 마치 큰 시간 복잡도가 나올 것 같지만 생각보다 시간이 걸리지 않는다는 점이 해당 시간 복잡도의 핵심이다. 마찬가지로 해당 사실을 이용하는 문제들을 추천하겠다.
Make Them Equal (#747 div2.C)
BOJ 6291 Brunhilda’s Birthday
트리 DP에서 노드의 개수가 $A$개와 $B$개인 두 서브트리를 $O(AB)$ 에 합치는 경우
이런 상황은 대충 연산의 상한선을 생각해보면, 간선의 개수만큼 합치는 연산이 발생하고 $O(n)$, 합치는 연산은 최대 $O(n^2)$의 시간이 걸리므로 $O(n^3)$이 될 것이라고 추측할 수 있다. 하지만 당연하지만 결과가 $O(n^3)$ 이라면 따로 포스팅을 하진 않았을 것이다. 놀랍게도 위의 상황의 시간 복잡도를 정확하게 계산하면 $O(n^2)$이 나오고, 이에 대한 증명은 더블 카운팅 기법을 사용하여 증명할 수 있다. 먼저 더블 카운팅이 무엇인지 알아보도록 하자.
더블 카운팅은 증명하는 방법이 일대일 대응을 이용한 증명과 유사하다고 느낄 수 있다. 그 이유는 둘 다 어떠한 등식을 증명 또는 유도하는데 사용되기 때문이다. 하지만 일대일 대응을 이용한 방식은 어떤 대상 A에 대하여 값을 구하려고 할 때, A와 동치인 상황을 통해 우회적으로 구하는 느낌이라 볼 수 있다. 반면에 더블 카운팅은 말 그대로 2번 센다는 의미이고, 같은 대상에 대하여 관점 1과 관점 2 이렇게 2개의 관점에서 바라보고 값을 구한다는 것이다. 2개의 증명방식을 정리하면 아래와 같다.
더블 카운팅
같은 상황(=대상)에 대하여
- A란 관점에서 구한다.
- B란 관점에서 구한다.
- 같은 대상을 세었으므로 A=B이다.
일대일 대응
- A의 값을 구하고 싶지만 어려움
- A와 동치관계인 B를 찾음 (A보다 쉬운 상황)
- B의 값을 구함
즉, 둘 다 A=B 라는 관계를 보이지만 약간의 차이가 있음을 알 수 있다.
이제 본격적으로 증명하고자 하는 내용을 다뤄보자. 위의 식은 아래와 같이 적어도 차이가 없으므로 아래 식을 증명하도록 하겠다.
$\displaystyle T(n)=\sum {min(sz(L),n)\times min(sz(R),n)}$ (L, R은 각각 현재 합치려는 두 트리, sz는 해당 서브트리의 사이즈)
Proof )
더블 카운팅 방식을 사용하도록 하자. 더블 카운팅은 같은 대상을 2개의 관점으로 세는 것이므로 먼저 상황을 가정하도록 하자.
위의 식은 이진트리에서의 상황으로 생각하여도 상관이 없으므로 (각 간선별로 트리가 합쳐지는 것을 이진트리에서 두 서브트리가 합쳐진다고 생각) 이진트리에 대하여 증명을 하도록 하겠다. 이진트리를 DFS preorder로 순회한 상황을 생각하자.
그러면 $min(sz(L),n)$ 이 의미하는 바는 임의의 서브트리에서 루트의 왼쪽 서브트리 L의 노드들 중, 가장 preorder number가 가장 큰 노드들을 최대 $n$ 개 고른 것이고, $min(sz(R),n)$ 는 오른쪽 서브트리 R에 대하여 preorder number가 가장 작은 $n$ 개를 골랐다고 생각할 수 있다. 이때 두 값을 곱했기 때문에 구하고자 하는 값은 이러한 쌍의 개수라고 볼 수 있다.
그렇다면 이러한 쌍은 어떻게 세야될까, 위의 관점에서 선택된 쌍 $(i,j)$ 를 생각하면 (단, $i,j$ 는 서브트리 L과 R에서 뽑힌 정점의 preorder number) 항상 $|i-j| \leq 2n$ 이 성립함을 알 수 있다.
따라서 $i$를 고정하고 $j$를 결정한다는 관점으로 바라봐도 더블 카운팅에 의해 같은 결과가 나올 것이다. $i$ 를 고정하는데 $O(n)$, 이때 가능한 $j$ 는 $O(n)$ 가지 이므로,
$\displaystyle T(n)=\sum {min(sz(L),n)\times min(sz(R),n)}=O(n^2)$ 임을 알 수 있다.
사실 위의 시간 복잡도를 처음 만난 문제는 19년도에 icpc 예선 준비과정 중에 풀었던 Parents 라는 문제였다. 당시에는 단순히 시간 커팅을 하고자 사이즈를 K개로 상한을 두었더니 시간안에 돌아가는 것을 보고, $O(NK^2)$이 커팅이 잘 됐나 보다라고 생각했다. 하지만 이후에 2019 KOI 2차 고등부 3번 를 풀면서 위의 사실을 공부하게 되었고, 이와 유사한 문제들을 몇 개 추천하도록 하겠다.
BOJ 17624 검은돌
BOJ 2584 트리 분할
BOJ 13120 트리의 변화
BOJ 16216 우산
BOJ 9013 Parents