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

빅 오는 훌륭한 도구이지만 유일한 도구는 아니다. 빅 오 표기법에서는 한 알고리즘이 다른 알고리즘보다 훨씬 빠른 경우에도 두 경쟁 알고리즘을 정확히 똑같은 방식으로 표현하기도 한다.

5-1 선택정렬

선택 정렬은 다음과 같은 단계를 따른다

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정하고 한 셀씩 이동하면서 현재까지 가장 작은 값을 기록한다.
2. 최솟값에 어느 인덱스에 들어 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다. 첫 번째 패스스루의 시작 인덱스는 0이고, 두 번째 패스스루의 시작 인덱스는 1일 것이다.
3. 매 패스스루는 1, 2 단계로 이뤄진다. 배열 끝에서 시작하는 패스스루에 도달할 때까지 패스스루를 반복한다.

5-2 선택 정렬 실제로 해보기

배열 [4, 2, 7, 1, 3]을 예제로 선택 정렬을 해보자.

첫 번째 패스스루를 시작하며 인덱스 0에 들어있는 값 4을 확인하고 하나밖에 확인 안 했으니 당연히 이 값이 최솟값이다. 이 인덱스를 변수에 저장한다.

1. 현 최솟값인 4와 2를 비교한다. 2가 4보다 작으므로 2가 최솟값이 된다.
2. 현재 최솟값인 2와 7을 비교한다. 여전히 2가 최솟값이다.
3. 현재 최솟값인 2와 1을 비교한다. 1이 더 작으므로 1이 최솟값이 된다.
4. 현재 최솟값인 1과 3을 비교한다. 배열의 끝에 도달했으므로 전체 배열의 최솟값이 1로 결정됐다.
5. 최솟값 1을 패스스루를 시작한 인덱스 0의 값과 교환한다. 1은 이제 올바른 위치에 있게된다. [1, 2, 7, 4, 3]
6. 두 번재 패스스루를 시작한다. 인덱스 0은 정렬됐으므로 인덱스 1부터 시작하며, 이 값 즉, 2가 현재 최솟값이 된다. 현재 최솟값인 2와 7을 비교한다. 여전히 2가 최솟값.
7. 현재 최솟값 2와 4를 비교한다. 여전히 2가 최솟값.
8. 현재 최솟값 2와 3을 비교한다. 배열의 끝에 도달했으므로 최솟값이 2로 확정됐다. 최솟값이 이미 올바른 위치에 있으므로 교환하지 않는다. [1, 2, 7, 4, 3]
9. 세 번째 패스스루를 시작한다. 인덱스 0, 1은 정렬됐으므로 인덱스 2부터 시작하며, 이 값 7이 현재 최솟값이 된다. 최솟값인 7과 4를 비교한다. 4가 7보다 작으므로 4가 최솟값이 된다.
10. 4와 3을 비교한다. 배열의 끝에 도달했으므로 최솟값이 3으로 확정됐다.
11. 최솟값 3을 패스스루를 시작한 인덱스 2의 값과 교환한다. [1, 2, 3, 4, 7] 올바르게 정렬됐지만 컴퓨터는 아직 모른다.
12. 세 번째 패스스루를 시작한다. 인덱스 3부터 시작하며, 이 값인 4가 현재 최솟값이 된다. 현재 최솟값과 7을 비교한다. 배열의 끝에 도달했으므로 최솟값이 4로 확정됐다. 최솟값이 이미 올바른 위치에 있으므로 교환하지 않는다. 마지막 셀을 제외한 모든 셀이 정렬되었고, 마지막 셀 역시 올바른 순서일 것이므로 전체 배열이 올바르게 정렬됐다.

5-2-1 선택 정렬 구현

const selectionSort = (array) => {
	for(let i = 0; i < array.length; i++){
		let lowestNumberIndex = i;
		for(let j = i + 1; j < array.length; j++){
			if(array[j] < array[lowestNumberIndex]){
				lowestNumberIndex = j;
			}
		}
		if(lowestNumberIndex !== i) {
			[array]i], array[lowestNumberIndex]] = [
				array[lowestNumberIndex],
				array[i]
			]
		}
	}
	return array;
};

변수 i 를 이용해 array의 각 값을 가리키며 끝에서 두 번째 값까지 살펴본다. 마지막 값을 시작하기 전에 이미 배열이 완전히 정렬되므로 마지막 값은 보지 않아도 된다.

lowestNumberIndex 에 현재 최솟값이 들어 있는 인덱스를 저장한다

각 패스스루에서는 루프를 한 번 더 돌면서 현재 최솟값보다 작은 값이 있는지 확인하고, 있다면 그 값의 인덱스를

lowestNumberIndex 에 저장한다. 안쪽 루프가 종료되는 시점에 패스스루에서의 최솟값 인덱스가 결정된다.

최솟값이 올바른 위치에 있지 않다면 패스스루를 시작했던 인덱스의 값과 최솟값 인덱스의 값을 교환한다.

5.3 선택 정렬의 효율성

선택 정렬은 비교, 교환이라는 두 종류의 단계를 포함한다.

비교는 (N-1) + (N-2) + (N-3) + ... + 1번을 진행한다. 교환은 한 패스스루당 최대 한 번 진행된다.최악의 시나리오에서는 교환을 패스스루를 도는 횟수만큼 진행해야 한다.

실제로 계산해보면, 선택 정렬의 최대 단계 수는 N²/2 단계 정도이다. 즉, O(N²)인 버블 정렬보다 선택 정렬이 두 배 더 빠르다.

5.4 상수 무시하기

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

빅 오 표기법은 상수를 무시한다. 즉, 지수가 아닌 수는 포함하지 않는다. 따라서 선택 정렬은 O(N²/2)가 아닌 O(N²)이다.

O(100N) 역시 O(N)으로 표시한다. 한 알고리즘이 다른 알고리즘과 표기법은 같지만 100배 더 빠를 수도 있다.

5.5 빅 오 카테고리

빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.

빅 오 표기법은 단지 알고리즘에 필요한 단계 수만 의미하지 않는다. 데이터가 늘어날 때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하다. O(N)은 직선 성장이지만 O(N²)은 지수 성장이다.

지수 성장은 어떤 형태의 O(N)과도 비교되지 않는, 완전히 다른 카테고리이다. 데이터가 커지면 언젠가 O(100N)보다 O(N²)이 더 느려지는 지점이 있다.

O(1), O(logN), O(N), O(N²)처럼 지금가지 다룬 모든 빅 오 유형이나 앞으로 나올 유형은 서로 차이가 큰 일반적인 빅 오 카테고리다.

같은 카테고리에 속하더라도 서로 처리 속도가 다를 수 있다. 서로 다른 카테고리에 속하는 알고리즘을 대조할 때는 빅 오가 완벽한 도구지만, 같은 카테고리에 속하는 두 알고리즘이라면 어떤 알고리즘이 더 빠를지 알기 위해 더 분석해야 한다.

5.5.1 실제 예제

1장에서 다뤘던 코드를 조금만 바꿔서 살펴본다.

const printNumbersVersionOne = (upperLimit) => {
  let number = 2;

  while (number <= upperLimit) {
    if (number % 2 === 0) {
      console.log(number);
    }
    number += 1;
  }
};

const printNumbersVersionTwo = (upperLimit) => {
  let number = 2;
  while (number <= upperLimit) {
    console.log(number);
    number += 2;
  }
};

2부터 upperLimit까지의 모든 짝수를 출력하는 두 가지 알고리즘이다.

첫 번째 알고리즘에선 모든 짝수를 출력하는데 N단계가 걸린다. upperLimit이 100이라면 100단계가 걸린다(실제로는 2부터 시작하므로 99단계가 걸린다). 따라서 O(N)이다.

두 번째 알고리즘에선 N/2단계가 걸린다. 하지만 상수를 버리고 O(N)이라고 표현한다.

두 번째 버전이 첫 번째 버전보다 두 배 빠르고 따라서 더 나은 방법이다. 즉, 빅 오 표기법으로는 똑같이 표현되더라도 어떤 알고리즘이 더 빠른지 알아내려면 분석해야 한다.

5.5.2 중요한 단계

5.5.1의 예제의 첫 번째 버전은 N단계가 필요하다고 말했는데, 과연 딱 N단계가 필요한가? 매 루프 안에서 여러 단계가 일어난다.

1. number가 2로 나눠떨어지는지 확인하는 비교 단계if(number % 2 ===0). 비교는 매 루프마다 일어난다.
2. 짝수일 때만 일어나는 출력 단계console.log(number). 출력은 한 번 걸러 일어난다.
3. 매 루프마다 실행되는 number += 1.

알고리즘의 빅 오를 표현할 때 모든 단계가 다 중요하다. 다만 빅 오 용어로 단계를 표현할 때 상수를 버리고 표현식을 단순화할 뿐이다.

위에서 분석한 단계를 모두 센다면 N + 0.5N + N이므로 2.5N 단계다. 하지만 상수 2.5를 제거하고 O(N)이라고 표현한다.

중요한 것은 루프 안에서 정확히 무슨 일이 일어나는지 보다는, **"실질적으로 루프가 실행되는 횟수"**이다.

5.6 마무리

이제 빅 오를 사용해 알고리즘이 대체로 얼마나 효율적인지 알 수 있고, 빅 오에서 같은 분류에 속하는 두 알고리즘도 비교할 수 있다.