[질문] 공간복잡도 logn으로 병합정렬 구현해볼만한가?

[익명(112.152)]

시간복잡도 nlogn 으로 머릿속으로 구상은 했는데

학부생 경험삼아 구현하기엔 배열 범위 다루기 너무 귀찮다..

[익명(58.143)]

정렬을 log n?

[익명(58.237)]

? 어렵나 그게

[다믜(damhiya)]

기본적으로 안됨. 공간복잡도 O(n)이 아니면 사실상 다른 알고리즘이지

[다믜(damhiya)]

https://en.m.wikipedia.org/wiki/Block_sort

[다믜(damhiya)]

in place 변종 병합정렬이 몇가지 있는걸로 앎

[익명(112.152)]

사실상 두 배열 비교해서 재배열 하는 알고리즘만 만지는 느낌이라 나름 명예 병합정렬일듯..?

[익명(112.152)]

보통 죄다 병합정렬 공간복잡도를 O(n)으로 취급하니까 나름 공간복잡도 O(logn)으론 구현하기 까다로운건가 싶어서 좋은경험으로 알아주나 했네 ㅎㅎㅈㅅ

[휘발성(reduxx)]

상수배 해서 쓰고지우고 하면 시간복잡도는 그대로니까 가능하지..않나?

[익명(7hr827gdufa3)]

당장 입력도 저장을 못하는데 그게 정렬이 될수가 없잖아 - dc App

[익명(112.152)]

정렬에서 공간복잡도 취급할때 보통 지 자신은 빼고 추가 메모리만 취급하는줄 알았네 ㄷㄷ

[익명(117.111)]

공간을 접는 마법사 ㄷㄷ

[익명(117.111)]

정렬 도중에 추가적으로 얼마냐 쓰냐를 줄이는걸 생각했나보네

[익명(112.152)]

넹 맞워요..