삽입 정렬은 효율적인 정렬 알고리즘 중 하나로, 최선의 경우에는 O(n), 평균 및 최악의 경우에는 O(n^2)의 시간 복잡도를 갖습니다.

최선의 경우

최선의 경우는 이미 정렬된 상태일 때입니다. 이때는 각 요소를 비교한 후 이동시키는 과정이 필요 없으므로, 내부 루프는 실행되지 않고 바깥쪽 루프만 실행됩니다. 따라서 O(n)의 시간 복잡도를 갖습니다.

최악 및 평균의 경우

최악 및 평균의 경우에는 모든 요소를 비교하고 이동해야 합니다. 이에 따라 O(n^2)의 시간 복잡도가 발생합니다.

참고 자료

• Introduction to Algorithms, Cormen et al. (2009)
• “Insertion Sort” - GeeksforGeeks link

위의 시간 복잡도 분석은 삽입 정렬 알고리즘의 종합적인 이해를 돕기 위한 것입니다.