[책] 누구나 자료구조와 알고리즘 - 6장 긍정적인 시나리오 최적화

 

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

사담

정리하는 습관을 들이고자 책을 읽고 내용을 정리하는 스터디를 시작하게 되었다.

이전까지의 내용은 시간이 되면 다시 정리하기로 하고, 지금부터 읽은 내용들부터라도 차근차근 정리하려고 한다.

 

정리

이전 장(챕터)까지 버블 정렬, 선택 정렬에 대한 알고리즘 효율성을 알아봤다.

두 정렬 알고리즘 모두 최악의 경우에 O(N^2)를 가지지만, 선택 정렬의 경우는 O(N^2 / 2)를 가지므로 약간 더 빠르다는 사실을 알 수 있었다.

(하지만 빅오 표기법에서는 상수를 제거하므로 선택 정렬도 최악의 경우 O(N^2)가 정확한 표기법이기는 하다)

 

이번 장(챕터)에서는 삽입 정렬까지 알아봤다.

결론적으로 삽입 정렬도 최악의 경우 O(N^2)의 효율성을 가져 위의 3가지 알고리즘 중에서 선택 정렬이 최악의 경우 제일 빠른 알고리즘 속도를 가진다고 생각할 수 있었다.

 

하지만 항상 최악의 경우를 생각하는 것 만이 좋은 해결 방법을 위한 정답은 아니었다.

최선, 최악의 경우는 굉장히 드물게 일어나고, 일반적으로 일어나는 경우(평균)는 다른 알고리즘 효율성을 가질 수 있기 떄문이었다.

따라서 다양한 경우(시나리오)를 생각하고, 그것에 맞는 선택을 하는 것이 좋은 선택이라는 것을 깨닫게 되었다.

	최선의 시나리오	평균 시나리오	최악의 시나리오
선택 정렬	N^2 / 2	N^2 / 2	N^2 / 2
삽입 정렬	N	N^2 / 2	N^2

- 거의 정렬된 데이터를 다룰 것이라 가정할 수 있는 경우 : 삽입 정렬

- 대부분 역순으로 된 데이터를 다룰 것이라 가정할 수 있는 경우: 선택 정렬

- 데이터가 어떨지 전혀 알 수 없을 경우: 둘 다 동일

 

또한, 빅오 표기법에서는 가장 높은 차수의 N만 남기고, 낮은 차수는 제거해야한다는 사실을 알게 되었다.