Tree Dp 시간복잡도 분석
Tree DP를 DFS를 이용해 구현할 때, 실제 시간복잡도는 코드를 보고 대충 생각한 것보다 작은 경우가 많다. 이 글에서는 그런 몇몇 케이스를 다룬다.
자식 노드의 결과를 합칠 때 자식 서브트리 크기에 대한 다항식 시간이 걸릴 경우
보통 Tree DP는 다음과 비슷한 함수를 만들고 루트 노드를 함수 인자로 넘겨 실행하면 풀 수 있다.
void dfs(int node) {
(dp_table[node] 초기화);
for (int next : children[node]) {
dfs(next);
}
(dp_table[next]들의 값을 이용해 dp_table[node] 계산);
}
dfs(root_node);
노드 갯수가 $N$개인 트리에서 노드 $n$의 자식이 $k_n$개 있고, 이 자식들을 루트로 하는 $k$개의 서브트리의 크기가 각각 $|s^n_1|$, $|s^n_2|$, … , $|s^n_{k_n}|$라 해 보자.
함수 마지막에서 자식 노드의 결과를 합치는데, 이 과정의 시간복잡도가 $|s^n_i| (1 \leq i \leq k_n)$에 대한 이차식이 되는 경우를 생각해보자.
최악의 경우 각 노드에 대해 각 $|s_i|$가 $O(N)$, 노드를 합치는 횟수가 $O(N)$이므로 dfs(root_node)의 시간복잡도는 $O(N^3)$이 될 것 같지만, 실제로는 $O(N^2)$가 된다.
$n$이 루트인 서브트리의 크기를 $|n|$, 이 노드의 결과를 구하는 시간을 $T(n)$이라 해 보자.
또한 자식 노드들의 결과를 합치는 시간복잡도가 $O(이차식)$이라는 것은, 자식 노드 $s^n_1$, $s^n_2$, … 의 결과를 합치는 데 $\sum_{1 \leq i \leq j \leq k_n} c |s^n_i| |s^n_j|$ ($c$는 상수) 이하의 시간이 걸린다는 뜻이다.
$n$의 자식들 $s^n_i$에 대해 $T(s^n_i) \leq d|s^n_i|^2 = O(|s^n_i|^2)$ ($d는 상수) 라고 가정해 보자. 그러면,
\[\begin{split} &T(n) \\ &= \sum_{1 \leq i \leq j \leq k_n} c \|s^n_i\| \|s^n_j\| + \sum_{1 \leq i \leq k_n} T(s^n_i) \\ &\leq \sum_{1 \leq i \leq j \leq k_n} c \|s^n_i\| \|s^n_j\| + \sum_{1 \leq i \leq k_n} d\|s^n_i\|^2 \\ &= \sum_{1 \leq i \lt j \leq k_n} c\|s^n_i\| \|s^n_j\| + \sum_{1 \leq i \leq k_n} (c+d)\|s^n_i\|^2 \\ &\leq \sum_{1 \leq i \lt j \leq k_n} 2e \|s^n_i\| \|s^n_j\| + \sum_{1 \leq i \leq k_n} e\|s^n_i\|^2 \quad \quad ({e > c + d}) \\ &= e \left( \sum_{1 \leq i \leq k_n} \|s^n_i\| \right) ^ 2 \\ &= e (\|n\|- 1)^2 = O(\|n\|^2) \end{split}\]가 되어 노드 $n$에 대해서도 $T(n) = O(|n|^2)$가 성립한다.
또한 base case인 리프 노드에 대해서는 $T(|n|) = O(1) < O(|n|^2)$ 이므로, 수학적 귀납법에 의해 전체 문제를 $O(N)$ 시간에 풀 수 있다.
저걸 잘 일반화하면, 자식 노드의 결과를 합치는 시간복잡도가 $|s^n_1|$, $|s^n_2|$, … , $|s^n_{k_n}|$ 에 대한 $p$차식이면, 전체 문제를 $O(N^p)$ 시간에 풀 수 있다는 것도 알 수 있다.
자식 노드를 합칠 때 자식 노드의 갯수에 대한 다항식 시간이 걸릴 경우
대충 이런 경우를 생각해보자.
void dfs(int node) {
(dp_table[node] 초기화);
for (int next : children[node]) {
dfs(next);
}
for (int next1 : children[node]) {
for(int next2 : children[node]) {
dp_table[node] = foo(dp_table[next1], dp_table[next2]);
}
}
}
dfs(root_node);
이때 함수 foo는 O(1) 시간에 실행된다고 하자.
이것도 대충 보면 위와 비슷한 이유로 $O(N^3)$ 시간이 걸릴 것 같다. 하지만 이것도 $O(N^2)$다.
위와 마찬가지로, $n$이 루트인 서브트리의 크기를 $|n|$, 이 노드의 자식 노드의 갯수를 $k_n$, 이 노드의 결과를 구하는 시간을 $T(n)$이라 해 보자.
자식 노드들의 결과를 합치는 시간복잡도는 $O({k_n}^2)$, 즉 $c{k_n}^2$ 이하이다 ($c$는 상수).
임의의 노드 $n$의 자식들 $s^n_i$에 대해 $T(s^n_i) \leq d|s^n_i|^2 = O(|s^n_i|^2)$ ($d는 상수) 라고 가정해 보자. 그러면,
\[\begin{split} &T(n) \\ &= c{k_n}^2 + \sum_{1 \leq i \leq k_n} T(s^n_i) \\ &\leq c{k_n}^2 + \sum_{1 \leq i \leq k_n} d\|s^n_i\|^2 \\ &= c \left( \sum_{1 \leq i \leq k_n} 1 \right) ^ 2+\sum_{1 \leq i \leq k_n} d\|s^n_i\|^2 \\ &\leq c \left( \sum_{1 \leq i \leq k_n} \|s^n_i\| \right) ^ 2+\sum_{1 \leq i \leq k_n} d\|s^n_i\|^2 \\ &\leq e \left( \sum_{1 \leq i \leq k_n} \|s^n_i\| \right) ^ 2+\sum_{1 \leq i \leq k_n} e\|s^n_i\|^2 \quad \quad ({e > c + d}) \\ &\leq 2e \left( \sum_{1 \leq i \leq k_n} \|s^n_i\| \right) ^ 2 \\ &= 2e (\|n\|- 1)^2 = O(\|n\|^2) \end{split}\]가 되어 위와 마찬가지로 수학적 귀납법에 의해 전체 문제를 $O(N^2)$에 해결할 수 있다. 이것도 자식 노드들의 결과를 합치는 시간복잡도는 $O({k_n}^p)$일 때 전체 문제를 $O(N^p)$에 해결할 수 있다고 일반화할 수 있다.
연습문제
BOJ 21141 - Kth Subtree
BOJ 17624 - 검은 돌
Leave a comment