근데 머지소트 nlgn이 머지 과정까지 합한 시간복잡도 아냐???

[에이시아(203.90)]

 맞지???

[Deskjet(163.239)]

시간복잡도가 그렇게 상세한 부분(혹은 하드웨어 의존)까지 나타내는 용도가 아니란다. 머지과정은 컴퓨팅 장치마다 속력이 다를 수도 있다.

[에이시아(203.90)]

책에 보니까 이렇게나와있는데 W(n) = W(h) + W(m) + h + m -1 W(h)하고 W(m)은 머지소트에서 두개로 분할되는거 그거 말한거고 h+m-1이 합병하는데 걸리는 시간이라는데...???

[에이시아(203.90)]

합병도 말하자면 분할된 두개의 배열을 가지고 인덱스 1부터 시작해서 비교해가면서 새로운 배열 S(k)에 집어넣는 과정 아냐???

[에이시아(203.90)]

결국 단위연산은 비교라는 거고 그리고 무엇보다 머지 과정을 빼고 계산하면 nlgn이 안나와 오늘 시험에 나왔었는데 안되더라고...

[에이시아(203.90)]

머지 과정도 단위연산이 존재하니까 포함시켜야 되는거 아냐??? 머지 과정도 시간을 꽤 잡아 먹잖아...

[에이시아(203.90)]

그지... 어제 물어봤엇는데 합병 시간이 오버헤드라고 하더라고... 근데 오버헤드라고 하기엔 중심 연산인데...

[에이시아(203.90)]

근데 그럼 합병 정렬하고 퀵 정렬하고 비교해서 시간 복잡도는 평균의 경우 같은데 퀵정렬이 더 빠르다고 하는 이유는 뭐야...???

[에이시아(203.90)]

합병 과정에 비교 말고 쓸데 없는 오버헤드가 많다 이말이야???

[에이시아(203.90)]

퀵소트가 최악의 경우 합병 정렬보다 느린데 n^2시간 복잡도야.

[에이시아(203.90)]

합병 정렬은 최악 = 평균 nlgn

[음..(211.180)]

퀵소트는 샘플만 적절히 뽑으면 워스트 케이스가 나올 확율은 무시해도 될만한 수준임

[음..(211.180)]

게다가 퀵소트는 어차피 인메모리에서만 하잖아. n^2나온들 별차이도 없지.

[에이시아(203.90)]

어쨋든 평균의 경우 시간복잡도는 같은데 퀵정렬이 그냥 조금 빠른 정도야??? 시간 복잡도는 같으니까..

[에이시아(203.90)]

어쨋든 n^2하고 nlgn은 차이가 좀 나는거지 데이터 갯수가많으면 많을수록...

[에이시아(203.90)]

근데 시간 복잡도는 평균의 경우같은데 왜 퀵 정렬이 합병 정렬보다 더 빠르다고 하는거지???

[에이시아(203.90)]

합병 정렬의 경우 머지과정도 고려한 시간 복잡도인데 딱히 오버헤드 들어갈데가 있는지도 모르겠고...

[에이시아(203.90)]

아... 대충 이해 됐어 답변 고마워

[음..(211.180)]

데이터가 많으면 많을 수록 차이가 나는건 맞는데, 데이터 천만건 모아 놓고 인메모리에서 퀵소트 할거 아니잖아. 결국 머지소트할텐데, 메모리에 들어가는 사이즈에선 퀵소트를 할테고, 이때 간혹가다 재수업게 n^2이 나온다고 해서 항상 nlogn 나온거랑 시간차이가 얼마나 되겠냐

[음..(211.180)]

저거보다 더빠른건 버켓소트가 있지. 더 빠른 소팅이 없다는건 상황의 제약을 주고 할때 얘기지.

[음..(211.180)]

머지 소트도 추가 공간을 n에 비례하게 쓸수 없다는 제약이 있으면 사용 못하니, 제약이 있는건 마찬가지고

[에이시아(203.90)]

결론은 합병 > 퀵???

[[성대아싸](skkuassa)]

시간복잡도는 증가율의 개념 속도는 말그대로 속도고요 [핡]