6장 긍정적인 시나리오 최적화

• 어떤 문제 해결을 위해 여러 알고리즘 중 하나를 선택할 때는, 모든 시나리오를 고려하는 능력이 필요하다.

1. 삽입 정렬

• 버블 정렬과 선택 정렬의 시간 복잡도는 O(N^2)으로 같지만 실제 실행되는 단계 수는 선택 정렬이 두 배 적다. 즉, 두 배 빠르다.
• 6장에서는 삽입 정렬에 대해 배우면서 최악의 시나리오가 아닌 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아본다.
• 삽입 정렬의 수행 순서
  1. 첫 번째 pass through에서 두 번째 셀의 값을 삭제하고 이 값을 임시 변수에 저장한다. 삭제한 공간은 공백으로 남는다.
  2. 공백 기준 왼쪽의 값과 차례대로 비교하여 올바른 위치에 임시 변수의 값을 삽입한다.
  3. 두 번째 pass through는 세 번째 셀의 값을 삭제하고, 위의 pass through를 반복한다.

2. 삽입 정렬 구현

fun main() {
	insertionSort(arrayOf(10, 9, 4, 6, 7, 8, 3, 2, 11, 1)).forEach { print("$it ") }
}

fun insertionSort(arr: Array<Int>): Array<Int> {
	for (i in 1 until arr.size) {
		var temp_value = arr[i]
		var position = i - 1
		while (position >= 0) {
			if (arr[position] > temp_value) {
				arr[position + 1] = arr[position]
				position--
			} else break
		}

		arr[position + 1] = temp_value
	}
	
	return arr
}

3. 삽입 정렬의 효율성

• 삽입 정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입 네 종류이다.
• 비교는 1 + 2 + 3 + … + N - 1번 일어난다.
• 시프트는 값을 한 셀 오른쪽으로 옮길 때마다 일어난다.
  • 배열이 역순으로 정렬되어 있다면(최악의 경우) 비교가 일어날 때마다 값을 오른쪽으로 시프트해야 한다.
  • 즉, 비교 횟수만큼 시프트가 일어난다.
• 배열로부터 temp_value를 삭제하고 다시 삽입하는 작업은 pass through당 한 번씩 일어난다.
• pass through는 항상 N - 1번이므로 결국 N - 1번의 삭제와 N - 1번의 삽입이 일어날 것이다.
• 즉, O(N^2 + N)이다.
• 그러나 빅 오 표기법은 가장 높은 차수의 N만 고려한다.
• O(N^2 + N) → O(N^2)
• 버블 정렬은 선택 정렬보다 두 배 느리고, 삽입 정렬은 버블 정렬보다 + N만큼의 단계가 더 존재한다.
• 그렇다면 정렬 속도는 항상 삽입 정렬 > 버블 정렬 > 선택 정렬 순일까?

4. 평균적인 경우

• 최악의 시나리오에서는 선택 정렬이 삽입 정렬보다 빠르다.
• 모든 시나리오 관점에서 삽입 정렬의 효율성을 검토해 보자.
• 최악의 시나리오에서는 모든 데이터를 비교하고 시프트하고, 최선의 시나리오에서는 어떤 데이터도 시프트하지 않는다.
• 평균 시나리오에서는 대체적으로 데이터의 반을 비교하고 시프트할 것이다.
• 즉, N^2 / 2 단계가 걸린다고 말할 수 있다.
• 그러나 빅 오 관점에서는 두 시나리오 모두 O(N^2)이다.
• 삽입 정렬은 시나리오에 따라 성능이 크게 좌우된다.
  • 최악: O(N^2)
  • 최선: O(N)
  • 평균: O(N^2 / 2)
• 선택 정렬은 최악부터 평균, 최선의 시나리오 모두 N^2 / 2단계가 걸린다.

6. 마무리

• 최선, 평균, 최악의 시나리오를 구분하는 능력은 기존 알고리즘을 최적화해서 훨씬 빠르게 만드는 것만큼이나 사용자 요구에 맞는 최적의 알고리즘을 고르는 핵심 기술이다.
• 최악의 경우를 대비하는 것도 좋지만 대부분은 평균적인 경우가 일어난다는 것을 명심하자.

 

- 7장은 여러 코드의 예시로, 블로그 포스팅은 스킵한다.