4알고리즘 분석

 

삽입 정렬 알고리즘의 계산 복잡도는 조금 생각해 볼만 한 점이 있습니다. 최선의 경우에 조금 독특한 결과가 나타나기 때문입니다. 삽입 정렬 알고리즘의 입력으로 이미 정렬이 끝난 리스트, 예를 들어 [1, 2, 3, 4, 5]와 같은 리스트를 넣어 주면 O(n)의 계산 복잡도로 정렬을 마칠 수 있습니다. 하지만 이런 경우는 특별한 경우입니다.

일반적인 입력일 때 삽입 정렬의 계산 복잡도는 선택 정렬과 같은 O(n²)입니다. 따라서 선택 정렬과 마찬가지로 정렬할 입력 크기가 크면 정렬하는 데 시간이 굉장히 오래 걸립니다.

삽입 정렬에 이어 문제 10과 11에서는 각각 병합 정렬과 퀵 정렬을 살펴보겠습니다. 병합 정렬과 퀵 정렬은 재귀 호출을 이용하여 선택 정렬이나 삽입 정렬보다 더 빠르게 정렬할 수 있는 효과적인 알고리즘입니다. 하지만 원리를 한 번에 이해하기에는 약간 어려울 수 있습니다.

따라서 선택 정렬과 삽입 정렬을 공부하면서 어렵다고 느낀 사람은 11장의 ‘잠깐만요’를 읽은 후 바로 12장의 ‘문제 12 이분 탐색’으로 넘어가도 괜찮습니다.