5장 빅 오를 사용하거나 사용하지 않는 코드 최적화

• 빅 오는 알고리즘을 비교하고 주어진 상황에 알맞은 알고리즘을 결정하게 해 주는 좋은 도구이지만, 유일한 도구는 아니다.

1. 선택 정렬

• 선택 정렬의 시퀀스

1. 배열의 각 셀을 왼쪽에서 오른쪽으로 확인하면서 어떤 값이 최솟값인지 판단하고 가장 작은 값을 기록한다.
2. 최솟값과 pass through를 시작했을 때의 값을 교환한다.
3. pass through를 반복한다.

2. 선택 정렬 실제로 해보기 & 3. 선택 정렬 구현 (Kotlin)

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

fun selectionSort(arr: Array<Int>): Array<Int> {
	for (i in arr.indices) {
		var lowestNumidx = i
		for (j in i + 1 until arr.size) {
			if (arr[j] < arr[lowestNumidx]) lowestNumidx = j
		}

		if (lowestNumidx != i) {
			var temp = arr[i]
			arr[i] = arr[lowestNumidx]
			arr[lowestNumidx] = temp
		}
	}

	return arr
}

3. 선택 정렬의 효율성

• 선택 정렬은 비교 & 교환의 두 단계로 이루어진다.
• 원소 N개로 이루어진 배열에서, 비교는 N - 1 + N - 2 + N - 3 + … + 1 번 일어난다.
• 교환은 한 pass through 당 최대 한 번 일어난다.
• 교환을 아예 안 할 수도 있다.

4. 상수 무시하기

• 하지만 빅 오 표기법에서는 선택 정렬과 버블 정렬을 정확히 같은 방식으로 설명한다.
• 즉, 빅 오 표기법은 상수를 무시한다.

5. 빅 오 카테고리

• 빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.
• O(N) 알고리즘과 O(N^2) 알고리즘의 효율성 차이는 너무 크기 때문에 실제로 알고리즘의 복잡도가 O(100N), O(N^2/4)이든 별로 중요하지 않다.
• 그래서 O(N)과 O(N^2)는 별개의 카테고리로 나눈다.
• 하지만 상기 이유로, 같은 카테고리의 알고리즘이라도 서로 처리 속도가 다를 수 있다.

6. 마무리

• 이제 빅 오를 사용하여 알고리즘이 대체로 얼마나 효율적인지 알 수 있고, 빅 오에서 같은 분류에 속하는 두 알고리즘(버블 정렬과 선택정렬)도 비교해 보았다.
• 그러나 알고리즘의 효율성을 비교할 때 고려해야 할 중요한 요인이 또 있다.
• 정의에 따르면 최악의 시나리오는 항상 일어나지 않는다.
• 대체로 일어나는 시나리오는 평균 시나리오다.
• 6장에서는 모든 시나리오를 고려하는 방법을 알아본다.