doyunh2011   9달 전

이진 세그 트리는 배운 적 있지만 삼진 세그 트리는 배운 적이 없는데

물리 공부하다가 난데없이(?) 떠올라서 작성해 보았어요...

preview

위에 것이 삼진 세그 트리 작성한 코드인데

혹시 삼진 세그 트리가 속도가 더 빠른데 이진 세그 트리 코드만이 자주 보이는 이유가 무엇일까요...
(삼진 세그 트리가 이 경우에서만 빠른 것이라던가, 아니면 삼진 세그 트리는 상대적으로 메모리를 많이 차지해서 그런 거라던가...)

궁금해서 질문 올려봅니다...

kuming19   9달 전

개인적인 의견으로는 그정도의 상수커팅으로는 크게 의미가 없어서일지 않을까 싶어요. 이진세그가 결국 구현자체는 더 쉬우니까요

luckyandykang   9달 전

삼진 세그먼트 트리의 상수가 이진 세그먼트 트리보다 작은가요? 처음 알게 되었네요

octane   9달 전

배열을 이진트리로 쪼개면 구간 하나를 덮기 위해 최대 2 log_2 N 정도의 구간이 필요하고  삼진트리로 쪼개면 구간 하나를 덮기 위해 최대 4 log_3 N 정도의 구간이 필요한 것 같습니다. 아마 이를 저격하는 데이터가 있다면 후자가 더 느릴 수도 있을 것 같네요.

luckyandykang   9달 전

생각을 조금 더 해보니, 애초에 k진 트리에서는 log_k N번의 단계 동안 k번씩 재귀 호출이 발생하니 시간복잡도는 k log_k N 정도가 나오는데, 수학적으로만 분석하면 2 log_2 N이 항상 3 log_3 N보다 크거나 같습니다.. 알고리즘에서 분석과 똑같이 맞지는 않겠지만 수식적으로 분석한 결과도 신기하네요

oh040411   9달 전

제 생각에는 이렇습니다. 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달 전

좋은 답변 감사드려요ㅠㅠ
새로운 내용을 배울 수 있었어요ㅠ

모두 행복한 하루 되길 빌게요

댓글을 작성하려면 로그인해야 합니다.