퀵소트는왜 2분탐색하냐 3분탐색하면 더 유리하지않냐?

[익명(118.47)]

log3n되는거아니냐?

[하기노(thorpedo)]

log2n이랑 차이가...? - 수포자

[d(125.177)]

3분 탐색하면 3분동안 탐색하잖아? 그럼 2분 짜장이나 카레는 타버릴텐데

[머학원생(pjsdream)]

log_2 나 log_3 이나 시간복잡도상으론 같은것

[20160525(circir6174)]

결국 상수배인데

[20160525(circir6174)]

nlog3 n = n(log2 n/log2 3)

[Panzer(penzer27)]

퀵소트를 어떻게 3등분하지 머지소트는 충분할거 같긴한데

[익명(220.122)]

어떻게 세등분할 수 있다는건지 궁금

[20160525(circir6174)]

피벗 2개로 나눈다는거 아님?

[20160525(circir6174)]

qsort xs = qsort xs1 ++ qsort xs2 ++ qsort xs3

[Panzer(penzer27)]

가능하긴하겠네

[익명(220.122)]

그런거라면 다른 하나의 피벗은 그냥 다음번 qsort에서 피벗으로 사용될걸 굳이 이번 qsort에서 찾아서 쓰는거밖에 안될거 같은데

[쾌청(223.62)]

두개만잇으면 1번으로 모든 대소관계가 가려지지만 3개면 최소2번 재수없으면 3번비교해야지 대소관계가 가려지지. log2n을 log3n으로 줄이자고 비교연산 비용을 2.5배로 늘리는멍청한짓