중앙값 계산, O(n) 알고리즘이 정답일까?

커뮤니티에서는 중앙값 계산의 최적 시간 복잡도 O(n)을 달성하는 퀵셀렉트(Quickselect) 알고리즘이 주요 논점으로 부상했다. 이는 배열을 정렬하지 않고도 특정 순위의 원소를 찾는 방식으로, 면접에서 즉석으로 구현하기에는 복잡도가 높다는 의견이 다수다. [vrolfs]는 이 알고리즘을 모르는 것은 해당 질문의 가치를 떨어뜨린다고 지적하며, [msangi]는 알고리즘 지식을 테스트하는 좋은 기회가 될 수 있다고 덧붙였다.

원본 글쓴이는 정렬 기반의 O(n log n) 접근 방식을 기본으로 제시했지만, [vrolfs]와 [dvogel]은 O(n) 알고리즘의 존재를 근거로 면접 질문으로서의 가치가 낮다고 비판했다. [dvogel]은 면접관의 의도가 기본적인 프로그래밍 능력 확인에 있다면, 단순 정렬 방식으로도 충분하다고 주장했다. 즉, 최적화된 알고리즘 구현 능력을 즉석에서 요구하는 것은 비현실적이라는 의견이 주를 이룬다.

중앙값 계산 함수 설계 시 데이터 정렬(Data Sorting)을 함수 내부에서 처리할지, 호출자에게 위임할지에 대한 논의가 있었다. 또한, 참조 전달(Pass by Reference) 시 원본 배열의 불변성(Immutability)을 유지해야 하는지, 가변성(Mutability)을 허용해도 되는지에 대한 API 디자인 관점의 토론이 이어졌다. [bediger4000]은 특히 C++이나 Go와 같은 언어에서 짝수 길이 배열의 중간값 계산 시 오버플로우(Overflow) 가능성을 지적하며, 데이터 타입(Data Type) 선택의 중요성을 강조했다.

중앙값 계산은 단순히 중간값을 찾는 것을 넘어 통계적 의미를 내포한다. [Yomguithereal]은 평균(Mean) 대비 중앙값(Median)의 장점을 논하며, 이상치(Outlier)에 덜 민감하다는 점을 강조했다. 또한, 짝수 길이 배열의 경우 두 중간값의 평균 외에도 선형 보간(Linear Interpolation) 등 다양한 정의가 가능하며, 이는 분위수(Quantiles) 논의로 확장될 수 있음을 시사했다.