누구나 자료구조와 알고리즘 - (6) 긍정적인 시나리오 최적화

 

 

 

 

지금까지는 최악의 시나리오만 생각하여 빅오를 추론했다. 하지마 최악의 시나리오 외에 고려할 사항들이 있다. 정렬의 종류에는 버블 정렬, 삽입 정렬, 선택 정렬이 있는데 최악의 시나리오만을 고려했을 때 선택 정렬이 가장 나은 방법이라고 생각할 수 있다. 하지만 평균 시나리오도 중요하게 고려해야 한다.

 

	삽입 정렬	선택 정렬
정의	임의로 첫번째 인덱스의 값을 삭제한 뒤 임시 변수에 담아놓고 왼쪽에 있는 값을 비교하여 임시 변수에 있는 값보다 크면 값을 오른쪽으로 시프트하고 공백에 임시 변수에 있는 값을 담는다.	최소값을 찾은 뒤 다음 인덱스와 교환한다.
최악의 시나리오	N²단계	N² / 2단계
평균 시나리오	N² / 2단계	N² / 2단계
최선의 시나리오	약 N단계	N² / 2단계

 

거의 정렬된 데이터를 다룰거라고 가정한다면 삽입 정렬을, 대부분 역순으로 정렬된 데이터를 다룰거라고 가정한다면 선택 정렬이 더 빠르다. 최악의 경우를 대비하는 것도 좋지만 대부분은 평균적인 경우가 일어난다는 점을 명심하자.

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.