Complexity of sorting 정렬 알고리즘의 계산 복잡도를 정리하는 내용입니다. 상한선은 당연히 최대치/최악의 경우를 나타내고 있으므로 guarantee라는 표현이 쓰였습니다. 하한선은 이보다 더 좋을 수 없는 최선의 경우가 증명된 것을 뜻합니다. 최적 알고리즘은 X라는 문제에 대해 최선의 것으로 증명된 경우에 해당하며 상한선과 하한선 사이에 위치합니다. Decision tree (for 3 distinct a, b, and c) 의사 결정 나무를 통해 정렬에 대한 결정을 시각화할 수 있습니다. 여기서는 각 비교를 합쳐 맨 마지막에 세 개의 값을 비교한 결과물을 얻어낼 수 있음을 보여주고 있습니다. 트리의 높이는 비교를 가장 많이 해야 하는 최악의 경우를 뜻하게 됩니다. Compare-base..
