Decision Tree Complexity for 3SUM

알고리즘을 모델링하는 여러 방법 중 하나는 Decision Tree이다. Decision Tree에서 알고리즘은 입력의 특정 부분을 읽어서 읽은 결과에 따라 YES / NO verdict를 결정하고, 비교 결과에 따라서 두 상태 중 하나로 분기한다. 예를 들어서 비교 정렬에서는 $x_i, x_j$ 를 읽은 다음에, $x_i - x_j$ 의 부호에 따라서 YES / NO verdict를 결정하고, 이 결과에 따라서 두 개의 자식 상태 중 하나로 분기한다.

Decision Tree의 최대 깊이는 보통 알고리즘 시간 복잡도의 lower bound를 구성하는데 자주 쓰인다. 비교 정렬에서는 결과 상태가 최소 $n!$ 개이니, 최대 깊이가 적어도 $\log_2 (n!) = O(n \log n)$ 이고, 그래서 모든 비교 정렬 알고리즘의 시간 복잡도는 적어도 $O(n \log n)$ 이다.

물론 모든 알고리즘이 $x_i, x_j$ 를 읽은 다음에 $x_i - x_j$ 의 부호에 따라서 YES / NO verdict를 결정할 필요는 없다. 기수 정렬마냥 $A[x_i] = i$ 같은 연산을 할 수도 있고, 아니면 $\exp(x_i) - \sqrt{x_j}$ 같은 뜬금없는 식을 계산할 수도 있다. 최소한 그런 걸 안하는 알고리즘들에 대해서는 그렇다는 것이다. (거의 모든 일반적인 알고리즘들이 저러한 연산을 안 / 못 하는 것을 경험적으로 알고 있으나, 이에 대한 formal argument가 있는지는 잘 모르겠다.)

다시 정렬의 예시로 돌아가서, 정렬은 Decision Tree의 최대 깊이가 최소 $O(n \log n)$ 이면서, 실제로 $O(n \log n)$ 의 깊이를 가지는 트리들이 여럿 알려져 있다 (Merge Sort, Heapsort 등등). 이 경우를 보면 알고리즘의 Decision Tree의 깊이와 실제 알고리즘의 시간 복잡도가 일치하는 것을 알 수 있다. 하지만 Decision Tree의 깊이는 짧지만 실제 그 깊이를 내는 알고리즘이 있는지 모르는 경우도 있다. 예를 들어 3SUM 문제가 그렇다.

Problem (3SUM). 수열 $a_1, a_2, \ldots, a_n$ 이 주어졌을 때, $a_i + a_j + a_k = 0$ 인 $1 \le i ,j, k \le n$ 이 있는지 판별하라.

정렬 문제처럼 Decision Tree에서 $x_i - x_j$ 의 부호만 알려준다면 절대 못 풀거 같으니, 다음과 같은 연산을 허용하자.

Definition ($s$-linear decision tree). 알고리즘은 $c_1, c_2, \ldots, c_s$ 와 $i_1, i_2, \ldots, i_s$ 를 제시한 후 $\sum_{1 \le k \le s} c_k a_{i_k}$ 의 부호를 알 수 있다 ($0$ 초과, $0$, $0$ 미만)

예를 들어, 3SUM의 $O(n^3)$ brute-force 알고리즘은 깊이 $O(n^3)$ 의 $3$-linear decision tree로 구현할 수 있다. 잘 생각해 보면 $O(n^2)$ two-pointer 알고리즘도 깊이 $O(n^2)$ 의 $3$-linear decision tree로 구현할 수 있다. 여기까지만 보면 여전히 Decision Tree의 깊이와 알고리즘의 시간 복잡도는 거의 일치하는 것 같다. 하지만 오늘 얘기할 알고리즘 (Grønlund, Pettie 2014) 은 3SUM을 $O(n^2 \log n)$ 시간과 $O(n^{3/2} \log n)$ decision tree 깊이에 해결한다. 사실 원본에서는 $O(n^{3/2} \sqrt{\log n})$ 깊이에 해결하지만, 어차피 후속 논문에서 $O(n^{3/2})$ 로 누가 줄여놨으니 여기서는 무시하자.

알고리즘은 다음과 같다. $4$-linear decision tree이다.

• 먼저 수열 $a$ 를 $O(n \log n)$ 시간에 정렬하자. (Decision Tree에서 $a_i -a_j$ 부호 물어봐서 $O(n \log n)$ 깊이에 가능)
• $g = \sqrt n$ 으로 잡고, 수열을 크기 $g$의 버킷으로 묶는다 (즉 $i$ 번 버킷에는 $a_{(i-1)g+1}, a_{(i-1)g+2}, \ldots, a_{ig}$ 가 있음). 편의상 $n = g^2$ 이고 $g$ 는 정수이다.
• $D = \bigcup_{1 \le i \le n/g, 1 \le j, k \le g} (a_{(i-1)g + j} - a_{(i-1)g + k})$ 로 정의하자. 즉 같은 버킷에서 온 $x, y$ 에 대해서 $a_x - a_y$ 의 합집합이다. $|D| = O(n^{3/2})$ 이다.
• $D$ 를 정렬하자. ($4$-linear decision tree니까 정렬 가능하다. 복잡도 깊이 모두 $O(n^{3/2} \log n)$ 이다.)
• 각 $1 \le i, j \le n/g$ 에 대해, $A_{i, j} = \{a_x + a_y \mid x \in [(i-1)g + 1, ig], y \in [(j-1)g + 1, jg]\}$ 로 정의하자. 즉 $x$ 는 $i$ 번 버킷에서, $y$ 는 $j$ 번 버킷에서 왔다.
• $A_{i, j}$ 를 정렬한다.
  • 복잡도는 $O(g^2 \log (g^2) \times (n/g)^2) = O(n^2 \log n)$ 이다.
  • Decision Tree 깊이는 0이다. $a_x + a_y < a_{x^\prime} + a_{y^\prime}$ 을 비교하는 것은, $a_x - a_{x^\prime} < a_y - a_{y^\prime}$ 을 비교하는 것과 동일하다. $x, x^\prime$ 은 한 버킷에서 왔고, $y, y^\prime$ 역시 한 버킷에서 왔다. 즉, 비교되는 두 원소 모두 $D$ 에 속한다. $D$ 를 정렬해 놨으니 상대 순서만 비교해서 $A_{i, j}$ 를 비교할 수 있다.
• 모든 $k$ 에 대해:
  • Two pointers를 사용하면 봐야 할 버킷 쌍이 $O(n/g)$ 개 임을 알 수 있다.
  • 각 버킷에 대해 $-a_k \in A_{i, j}$ 인지 이분 탐색으로 테스트한다.
  • 복잡도 깊이 모두 $O(n^{3/2} \log n)$ 이다.

고로 위 알고리즘은 Decision Tree 복잡도와 실제 알고리즘의 복잡도가 다른 경우에 속한다. 당연하지만, 쓸데없는 연산을 하면 실제 알고리즘의 복잡도는 Decision Tree와 별개로 무한정으로 늘릴 수 있다. 그러니 위 알고리즘에서 낭비되는 연산이 있는 건 아닌지를 생각해 볼 수도 있을 것이다. 현재 각 decision tree 콜에서 평균 $O(\sqrt n)$ 정도의 연산을 낭비 하고 있다고 하면, 이 낭비를 평균 $O(n^{1/2 - \epsilon})$ 으로만 줄여도 3SUM Conjecture를 반증할 수 있다.

여담으로 $k$-linear decision tree에서 $k$-SUM의 깊이는 $k$ 가 짝수일 때 $\Omega(n^{k/2})$, 홀수일 때 $\Omega(n^{(k+1)/2})$ 여야 함이 알려져 있다. (Erickson 1995) 즉 $3$-linear decision tree에서는 $O(n^2)$ 보다 잘 할 수 없고, $4$ 인 게 중요하다.