해설 보기
정답(가)는 ≥, (나)는 ≤ 로 연결한 것이 옳습니다.
핵심 개념
빅오(O) 표기법의 형식적 정의
빅오 표기법은 알고리즘 수행시간의 '상한(upper bound)'을 나타내는 점근적 표기법입니다. 형식적 정의는 "어떤 양의 상수 c와 n0이 존재하여 모든 n ≥ n0에 대하여 f(n) ≤ c·g(n)을 만족하면 f(n) ∈ O(g(n))"입니다. 여기서 두 부등호의 방향을 구분하는 것이 핵심입니다. n ≥ n0은 '충분히 큰 입력에서부터'라는 뜻으로, 작은 n에서의 예외적인 값은 무시하겠다는 의미입니다. 반면 f(n) ≤ c·g(n)은 그 구간에서 f(n)이 c·g(n)을 결코 넘지 않는다는 뜻으로, g(n)이 f(n)의 천장 역할을 한다는 의미입니다. 참고로 하한을 나타내는 오메가(Ω)는 f(n) ≥ c·g(n)으로 부등호가 반대이고, 세타(Θ)는 상한과 하한을 동시에 만족하는 경우입니다.
선지별 해설
①(가) ≥는 맞지만 (나)를 ≥로 두면 f(n) ≥ c·g(n)이 되어 하한 조건이 됩니다. 이는 빅오가 아니라 오메가(Ω) 표기법의 정의이므로 틀렸습니다.
②(가)를 ≤로 두면 'n ≤ n0인 모든 n', 즉 작은 입력 구간만 보겠다는 뜻이 되어 '충분히 큰 n에 대한 점근적 분석'이라는 취지에 어긋나므로 틀렸습니다.
③(가)의 ≤도 틀렸고 (나)의 ≥도 상한이 아닌 하한을 뜻하므로, 두 자리 모두 잘못 연결된 선지입니다.
④(가) n ≥ n0으로 '충분히 큰 모든 n'을 지정하고, (나) f(n) ≤ c·g(n)으로 c·g(n)이 f(n)의 상한임을 나타냅니다. 이것이 O(g(n))의 표준 정의와 정확히 일치합니다.
해설 보기
정답퀵 정렬은 피벗을 기준으로 멀리 떨어진 원소를 교환하므로 대표적인 불안정 정렬입니다.
핵심 개념
안정 정렬(stable sort)의 판별
안정 정렬이란 정렬 키의 값이 같은 원소들이 정렬 전후에도 원래의 상대적 순서를 그대로 유지하는 정렬을 말합니다. 예를 들어 (3, A)와 (3, B)가 이 순서로 들어 있었다면 정렬 후에도 (3, A)가 (3, B)보다 앞에 있어야 안정 정렬입니다. 안정성은 다중 키 정렬(1차로 이름순, 2차로 점수순 등)에서 앞선 정렬 결과를 보존해야 할 때 중요합니다. 대표적으로 버블 정렬, 삽입 정렬, 병합 정렬, 계수 정렬은 안정 정렬이고, 퀵 정렬, 선택 정렬, 힙 정렬, 셸 정렬은 불안정 정렬로 분류합니다. 불안정해지는 이유는 대부분 '멀리 떨어진 원소끼리 교환(swap)'하는 동작 때문인데, 이 과정에서 같은 값 원소의 앞뒤 순서가 뒤바뀔 수 있습니다.