개인적인 의견으로는 그정도의 상수커팅으로는 크게 의미가 없어서일지 않을까 싶어요. 이진세그가 결국 구현자체는 더 쉬우니까요
2042번 - 구간 합 구하기
삼진 세그먼트 트리의 상수가 이진 세그먼트 트리보다 작은가요? 처음 알게 되었네요
생각을 조금 더 해보니, 애초에 k진 트리에서는 log_k N번의 단계 동안 k번씩 재귀 호출이 발생하니 시간복잡도는 k log_k N 정도가 나오는데, 수학적으로만 분석하면 2 log_2 N이 항상 3 log_3 N보다 크거나 같습니다.. 알고리즘에서 분석과 똑같이 맞지는 않겠지만 수식적으로 분석한 결과도 신기하네요
제 생각에는 이렇습니다. BOJ Book에 있는 구현체를 기준으로 설명하겠습니다. 세그먼트 트리의 쿼리를 두 부분으로 나누어 생각하면, (1) 재귀 호출 부분(line 8~9)과 (2) 두 노드를 합치는 부분(line 10)입니다.
이때 재귀 호출은 2진 트리에서 2번, 3진 트리에서 3번 발생합니다. 그런데 두 노드를 합치는 연산은 2진 트리에서 덧셈 1번, 3진 트리에서 덧셈 2번 (lsum + msum + rsum)입니다.
$b$진 세그먼트 트리의 깊이는 $O(\log_b N)$이므로, 각 부분의 시간복잡도는 다음과 같습니다.
(재귀 호출) 2진 트리: $2 \log_2 (N)$, 3진 트리: $3 \log_3 (N)$. 이 경우 3진 트리가 미세하게 (5%정도) 더 빠릅니다.
(노드 병합) 2진 트리: $\log_2 (N)$, 3진 트리: $2 \log_3 (N)$. 이 경우 3진 트리가 25% 정도 느립니다.
이 문제에서 노드를 합치는 연산은 덧셈 하나로 아주 가벼운 연산에 속합니다. 따라서 재귀 호출이 비교적 무겁고, 구현체의 상수 차이로 인해서 3진 트리가 더 빠를 수 있을 것 같습니다.
반면 어려운 문제들의 경우 노드에 복잡한 구조체를 넣어서 노드를 합치는 연산 자체가 상당히 무거운 경우가 있습니다. 이런 경우 이진 세그먼트 트리를 쓰는 것이 더 빠를 것입니다. 사실 노드 3개를 합치는 것 자체가 노드 2개 합치기를 두번 하는 것이기 때문에, 이진 트리 쪽이 구현하기 쉽기도 하구요.
좋은 답변 감사드려요ㅠㅠ
새로운 내용을 배울 수 있었어요ㅠ
모두 행복한 하루 되길 빌게요
댓글을 작성하려면 로그인해야 합니다.
doyunh2011 9달 전
이진 세그 트리는 배운 적 있지만 삼진 세그 트리는 배운 적이 없는데
물리 공부하다가 난데없이(?) 떠올라서 작성해 보았어요...
위에 것이 삼진 세그 트리 작성한 코드인데
혹시 삼진 세그 트리가 속도가 더 빠른데 이진 세그 트리 코드만이 자주 보이는 이유가 무엇일까요...
(삼진 세그 트리가 이 경우에서만 빠른 것이라던가, 아니면 삼진 세그 트리는 상대적으로 메모리를 많이 차지해서 그런 거라던가...)
궁금해서 질문 올려봅니다...