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

5.1 선택 정렬

선택 정렬(Selection Sort)이란?
가장 작은 데이터를 찾아 가장 앞의 데이터와 교환하는 알고리즘

선택 정렬은 아래 단계에 따라 실행된다.

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하며 어떤 값이 최솟값인지 결정한다.
   (한 셀씩 이동하며 현재까지 가장 작은 값의 인덱스를 저장)

   데이터	2	5	1	3
   index	0	1	2	3
   	👆

   현재 최솟값(index) : 2(0)

   데이터	2	5	1	3
   index	0	1	2	3
   		👆

   현재 최솟값(index) : 2(0)

   데이터	2	5	1	3
   index	0	1	2	3
   			👆

   현재 최솟값(index) : 1(2)

   데이터	2	5	1	3
   index	0	1	2	3
   				👆

   현재 최솟값(index) : 1(2)

2. 최솟값의 위치를 알았으므로, 패스스루를 실행하여 해당 값과 최솟값을 교환한다.
   첫 번째 패스스루에서는 해당 값이 인덱스 0에 위치한 2이고, 2와 최솟값 1을 교환한다.

   변경 전 : [2, 5, 1, 3]
   변경 후 : [1, 5, 2, 3]

3. 매 패스스루는 위의 1~2단계로 이루어지며, 마지막 데이터로 시작하는 패스스루에 도달할 때까지 반복된다. 그리고 마지막 패스스루에서는 배열이 모두 정렬되어 있다.

5.2 선택 정렬 실제로 해보기

첫 번째 패스스루

1. 인덱스 0을 확인한다. 현재까지 중 가장 작으므로 최솟값 변수에 저장한다.

   데이터	4	2	7	1	3
   index	0	1	2	3	4
   	👆

   현재 최솟값(index) : 4(0)
   
   그리고 인덱스 1을 확인한다. 최솟값과 비교하여 2가 더 작으므로 최솟값 변수에 저장한다.

   데이터	4	2	7	1	3
   index	0	1	2	3	4
   		👆

   현재 최솟값(index) : 2(1)

2. 인덱스 2를 확인한다. 최솟값과 비교하여 7은 2보다 크므로 다음으로 넘어간다.

   데이터	4	2	7	1	3
   index	0	1	2	3	4
   			👆

   현재 최솟값(index) : 2(1)

3. 인덱스 3을 확인한다. 최솟값과 비교하여 1이 더 작으므로 최솟값 변수에 저장한다.

   데이터	4	2	7	1	3
   index	0	1	2	3	4
   				👆

   현재 최솟값(index) : 1(3)

4. 마지막 인덱스를 확인한다. 최솟값과 비교하여 3은 1보다 크므로 전체 배열에서 최솟값은 1로 결정됐다.

   데이터	4	2	7	1	3
   index	0	1	2	3	4
   					👆

   현재 최솟값(index) : 1(3)

5. 최솟값이 결정됐으므로, 첫 번째 패스스루를 시작했던 인덱스 0과 최솟값 1을 교환한다.

   데이터	1	2	7	4	3
   index	0	1	2	3	4
   	👆

두 번째 패스스루

첫 번째 패스스루에서 배열의 첫 번째 셀인 인덱스 0은 이미 정렬된 상태이므로 인덱스 1부터 시작한다.
인덱스 1의 값인 2는 두번째 패스스루를 시작하는 현재 최솟값이다.

6. 인덱스 2를 확인한다. 최솟값과 비교하여 7은 2보다 크므로 다음으로 넘어간다.

   데이터	1	2	7	4	3
   index	0	1	2	3	4
   	💯		👆

   현재 최솟값(index) : 2(1)

7. 인덱스 3을 확인한다. 최솟값과 비교하여 4는 2보다 크므로 다음으로 넘어간다.

   데이터	1	2	7	4	3
   index	0	1	2	3	4
   	💯			👆

   현재 최솟값(index) : 2(1)

8. 마지막 인덱스를 확인한다. 최솟값과 비교하여 3는 2보다 크므로 두 번째 패스스루의 최솟값은 2이며, 두 번째 패스스루를 시작한 인덱스 1의 자리에 이미 위치해있으므로 교환이 일어나지 않고 패스스루가 종료된다.

   데이터	1	2	7	4	3
   index	0	1	2	3	4
   	💯				👆

   현재 최솟값(index) : 2(1)

세 번째 패스스루

첫 번째와 두 번째 패스스루에서 인덱스 0과 인덱스 1의 자리가 이미 정렬되었으므로 인덱스 2에 위치한 7을 최솟값으로 저장하고 시작한다.

9. 인덱스 3을 확인한다. 4는 7보다 작으므로 최솟값 변수에 저장한다.

   데이터	1	2	7	4	3
   index	0	1	2	3	4
   	💯	💯		👆

   현재 최솟값(index) : 4(3)

10. 마지막 인덱스를 확인한다. 3은 4보다 작으므로 최솟값 변수에 저장함으로써 세 번째 패스스루의 최솟값은 3으로 결정됐다.

    데이터	1	2	7	4	3
    index	0	1	2	3	4
    	💯	💯

    현재 최솟값(index) : 3(4)

11. 세 번째 패스스루를 시작한 인덱스 2의 값인 7과 최솟값 3을 교환한다.

    데이터	1	2	3	4	7
    index	0	1	2	3	4
    	💯	💯	👆

네 번째 패스스루

데이터를 눈으로 보고있는 사람은 현재까지의 배열이 이미 정렬된 상태라는 것을 확인할 수 있지만,
컴퓨터는 알지 못하기 때문에 네 번째 패스스루를 실행해야 한다.

인덱스 0, 인덱스 1, 인덱스 2의 자리는 앞선 패스스루들에서 이미 정렬된 상태이므로 네 번째 패스스루는 인덱스 3에서 시작하며 4를 현재 최솟값으로 저장하고 시작한다.

12. 마지막 인덱스를 확인한다. 7은 4보다 크므로 4가 네 번째 패스스루의 최솟값으로 결정됐다.
    4는 네 번째 패스스루를 시작한 인덱스 3의 자리에 이미 위치해있으므로 교환이 일어나지 않고 패스스루가 종료된다.

    데이터	1	2	3	4	7
    index	0	1	2	3	4
    	💯	💯	💯	👆

이로써 마지막 셀을 제외한 모든 셀이 올바르게 정렬되었고,
마지막 셀 역시 마지막 순서에 위치해있이므로 전체 배열이 모두 정렬됐다.

코드로 구현한다면

기본 코드

function selectionSort(array) {
	for (let i = 0; i < array.length - 1; i++) {
    	let lowestIndex = i;
      
      	for (let j = i+1; j < array.length; j++) { 
        	if (array[j] < array[lowestIndex]) {
            	lowestIndex = j;
            }
        }
      
      	if (lowestIndex !== i) {
        	let swap = array[i];
          	array[i] = array[lowestIndex];
          	array[lowestIndex] = swap;
        }
    }
  
  	return array;
}

해설

function selectionSort(array) {
  	// array의 첫 번째 인덱스부터 array.length - 1까지 루프 순회
  	// 마지막 인덱스를 확인할 때는 이미 정렬이 완성된 상태이므로 확인하지 않아도 된다.
	for (let i = 0; i < array.length - 1; i++) {
      	// 현재까지의 최솟값 저장
    	let lowestIndex = i;
      
      	// i를 제외하고 나머지 값들을 '모두' 순회하며 더 작은 값이 있는지 확인
      	// 더 작은 값이 있을 경우 최솟값 변수에 저장한다.
      	for (let j = i+1; j < array.length; j++) { 
        	if (array[j] < array[lowestIndex]) {
            	lowestIndex = j;
            }
        }
      
      	// 최솟값의 위치가 패스스루를 시작한 위치, 즉 i에 위치해 있으면 건너뛰고
      	// 그렇지 않은 경우에는 올바른 정렬을 위해 i와 최솟값의 위치를 교환한다.
      	if (lowestIndex !== i) {
        	let swap = array[i];
          	array[i] = array[lowestIndex];
          	array[lowestIndex] = swap;
        }
    }
  
  	// 정렬된 배열을 반환
  	return array;
}

5.3 선택 정렬의 효율성

선택 정렬 알고리즘 버블 정렬과 같이 '비교와 교환' 이라는 두 가지 중요한 단계를 포함한다.
즉, 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교하고, 최솟값을 올바른 위치에 있는 교환한다.

비교(comparison) : 어느 쪽이 더 큰지 두 수를 비교
교환(swap) : 정렬을 위해 두 수를 교환

비교

🤔 원소가 5개라면 총 몇 번의 비교를 해야 할까?

5.2 예제에서 5개의 원소를 가진 배열로 선택 정렬을 했을 때,

• 첫 번째 패스스루 : 4번의 비교 수행
• 두 번째 패스스루 : 3번의 비교 수행
• 세 번째 패스스루 : 2번의 비교 수행
• 네 번째 패스스루 : 1번의 비교 수행

따라서, $4+3+2+1=10번$ 의 비교를 수행했다.
만약 원소가 $N$개라면 $(N−1)+(N−2)+(N−3)...+1번$의 비교를 수행한다.

교환

선택 정렬에서 교환은 각 패스스루당 최대 1번 일어난다.
패스스루의 최솟값의 위치에 따라 교환을 하느냐, 마느냐 둘 중 하나이기 때문이다.

😰 배열이 역순으로 정렬되어 있는 최악의 시나리오에서는...?

매 패스스루마다 각 1번의 교환을 빠짐없이 수행해야 한다.

🤓 데이터가 $N$개 일 때 버블 정렬과 선택 정렬을 비교해보자.

데이터 원소 N개	버블 정렬에서 최대 단계 수	선택 정렬에서 최대 단계 수
5	20	14 (10번 비교 + 4번 교환)
10	90	54 (45번 비교 + 9번 교환)
20	380	199 (180번 비교 + 19번 교환)
40	1560	819 (819번 비교 + 39번 교환)
80	6320	3239 (3160번 비교 + 79번 교환)

위와 같이 선택 정렬은 버블 정렬보다 약 절반 정도의 단계 수를 가진다.
즉, 선택 정렬이 버블 정렬보다 2배 빠르다고 볼 수 있다.

5.4 상수 무시하기

그러나 빅 오 표기법에서는 선택 정렬의 알고리즘을 버블 정렬과 똑같은 $O(N^2)$로 표기한다.

앞서 선택 정렬이 버블 정렬보다 약 절반의 최대 단계를 수행한다고 했다.
이를 테이블로 표현하면 아래와 같다.

데이터 원소 N개	$N^2 / 2$	선택 정렬에서 최대 단계 수
5	$5^2 / 2 = 12.5$	14 (10번 비교 + 4번 교환)
10	$10^2 / 2 = 50$	54 (45번 비교 + 9번 교환)
20	$20^2 / 2 = 200$	199 (180번 비교 + 19번 교환)
40	$40^2 / 2 = 800$	819 (819번 비교 + 39번 교환)
80	$80^2 / 2 = 3239$	3239 (3160번 비교 + 79번 교환)

🤨 그런데 왜 $O(N^2)$로 표기하나요?

왜냐하면 빅 오 표기법은 상수를 무시하기 때문이다. 지수가 아닌 수는 포함하지 않고 버린다는 뜻이다.
즉, $N^2 / 2단계$가 필요했지만 빅 오 표기법에서는 $/ 2$를 버리고 $O(N^2)$로만 표기한다.

아래와 같은 빅 오 표기법 모두 상수를 무시한 또 다른 예이다.

• $N / 2단계$ : 지수가 아닌 숫자 2를 버리고 $O(N)$으로 표기
• $N^2 + 10단계$ : 지수가 아닌 숫자 10을 버리고 $O(N^2)$으로 표기
• $2N단계$ (= N * 2) : 지수가 아닌 숫자 2를 버리고 $O(N)$으로 표기

😧 100N단계는 N단계의 100배가 더 걸리는데 똑같이 $O(N)$인가요?

그렇다.

같은 빅 오 표기법으로 표현되지만 한 쪽이 다른 한 쪽보다 100배 빠를 수 있다.
위에서 살펴본 선택 정렬은 버블 정렬과 같이 빅 오로는 모두 $O(N^2)$으로 표현되지만 실제로는 버블 정렬보다 2배 가량 빠른 알고리즘이다.

5.5 빅 오 카테고리

빅 오 표기법이 상수를 무시하는 이유는 일반적인 카테고리의 알고리즘 속도만을 고려하기 때문이다.

• 145cm 키를 가진 사람 (A)
• 188cm 키를 가진 사람 (B)
• 191cm 키를 가진 사람 (C)
• 151cm 키를 가진 사람 (D)

위와 같이 각각의 키를 가진 사람이 있을 때 굳이 모든 사람마다 "A 사람은 145cm의 작은 키를 가진 사람", "C 사람은 191cm의 큰 키를 가진 사람"이라고 모두 표현하기 보다 "키가 큰 사람"과 "키가 작은 사람"과 같이 일반적으로 표현해도 키의 차이를 나타내기 충분하다.

알고리즘의 효율성 측면에서도 $O(N)$이 실제로 $O(2N)$이던지 $O(100N)$이던지, 이를 중요하게 생각하지 않고 그저 $O(N)$으로 표현하는 것이다.

3.2 빅 오의 본질에서도 빅 오 표기법은 데이터가 늘어날 때 알고리즘 단계 수가 어떻게 되는지, 즉 그래프에서 어떤 궤적을 그리는지를 중요하다고 했다.

$O(N)$은 직선 성장(straight growth)을 보인다. 즉 단계 수가 데이터에 일정 비율로 비례하여 직선을 그리며 증가한다. 그러나 이와 달리 $O(N^2)$는 지수 성장(exponential growth)을 보이며 직선 성장과는 완전히 다른 선을 그리며 증가하는 것을 볼 수 있다.

이처럼 일반적인 카테고리 관점에서 $O(N)$과 $O(N^2)$은 완전히 다른 카테고리이다.
$O(N)$에 어떤 수를 곱해봐도 $O(N^2)$이 더 느리다는 것을 알 수 있다.

$O(1)$, $O(logN)$, $O(N)$, $O(N^2)$ 모두 일반적인 빅 오 카테고리 중 하나이며,
지수가 아닌 수를 아무리 곱하거나 나눈다고 해도 카테고리 자체가 바뀌지 않는다.

버블 정렬과 선택 정렬도 마찬가지로 각 알고리즘 수행에 소요되는 처리 속도가 세부적으로는 다르지만 기본적으로는 $O(N^2)$ 이라는 큰 카테고리 안에 속한 알고리즘이다. 서로 다른 카테고리에 속한 알고리즘을 비교할 때에는 빅 오 표기법으로 충분하지만, 같은 카테고리 안에 속하는 알고리즘을 비교할 때에는 더 깊은 분석이 필요하다.

예제

1.3 속도 측정에서 다뤘던 코드에서 기존 100으로 정해져있던 상한선을 매개변수로 받는 것으로 수정하여 모든 짝수를 출력하는 알고리즘이다.

• 변경 전

function test1() {
	let num = 2;
  	
  	while (num <= 100) {
    	if (num % 2 === 0) console.log(num);
      	num += 1;
    }
}

function test2() {
	let num = 2;
  	
  	while (num <= 100) {
    	if (num % 2 === 0) console.log(num);
      	num += 2;
    }
}

• 변경 후

function test1(limit) {
	let num = 2;
  	
  	while (num <= limit) {
    	if (num % 2 === 0) console.log(num);
      	num += 1;
    }
}

function test2(limit) {
	let num = 2;
  	
  	while (num <= limit) {
    	if (num % 2 === 0) console.log(num);
      	num += 2;
    }
}

test1 함수에서는 limit까지 1씩 증가하기 때문에 시간 복잡도는 $O(N)$이다.

test2 함수에서는 2씩 증가하기 때문에 정확히 말하면 $N / 2단계$가 소요되지만 빅 오 표기법에서는 상수를 무시하기 때문에, 즉 지수가 아닌 숫자는 버리고 표현하기 때문에 똑같이 $O(N)$이다.

test2 함수가 test1 함수보다 2배 빠르지만 빅 오 표기법으로는 똑같이 표현된다. 두 함수 모두 $O(N)$이라는 같은 카테고리 안에 속한 알고리즘이라고 볼 수 있고, 이 중 어떤 알고리즘이 더 빠른지 알아내기 위해서는 더 깊은 분석을 해야 한다.

분석

test1 함수는 반복 루프를 $N$번 실행하기 때문에 $N$단계가 소요된다.

👀 하지만 정말로 정확히 N단계만 소요됐을까?

1. if (num % 2 === 0) 부분은 매 루프마다 일어난다.
2. console.log(num) 부분은 짝수일 때만 실행되므로 한 번 걸러 일어난다.
3. num += 1 부분은 매 루프마다 일어난다.

자세히 분석하면 위처럼 여러 단계가 일어난다고 볼 수 있다.

그러나 빅 오로 표기했을 때 상수를 버리고 $N$이라고 표현하는 이유는
정확히 무슨 일이 일어나는지 보다 실질적으로 반복 루프가 실행되는 횟수에 더 초점을 맞추기 때문이다.

실습

1. $4N + 16단계$가 소요되는 알고리즘의 시간 복잡도는?

정답 : $O(N)$
빅 오 표기법에서는 지수 외 상수는 무시되기 때문에 4배와 +16은 제외하고 표기한다.

2. $2N^2단계$가 소요되는 알고리즘의 시간 복잡도는?

정답 : $O(N^2)$
빅 오 표기법에서는 지수 외 상수는 무시되기 때문에 2배는 제외하고 표기한다.

3. 다음 함수의 시간 복잡도는?

function doubleThenSum(array) {
	let doubleArray = [];
  	let sum = 0;
  
  	array.forEach(num => doubleArray.push(num * 2));
  	doubleArray.forEach(num => sum += num);
  
  	return sum;
}

정답 : $O(N)$
for문을 2번 반복하므로 $2N$이지만 지수가 아닌 상수는 무시하므로 2배는 제외하고 표기한다.

4.다음 함수의 시간 복잡도는?

function multipleCases(array) {
	array.forEach(string => {
    	console.log(string.toUpperCase());
      	console.log(string.toLowerCase());
      	conso.e.log(string.charAt(0).toUpperCase() + string.slice(1).toLowerCase());
    });
}

정답 : $O(N)$
데이터 수만큼 1번씩 반복하고 for문 내부적으로 3개의 단계가 있기 때문에 $3N$이지만 상수는 제외하고 표기한다.

5. 다음 함수의 시간 복잡도는?

function processArray(array) {
    for (let i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            for (let j = 0; j < array.length; j++) {
                console.log(array[j] + array[i]);
            }
        }
    }
}

정답 : $O(N^2)$
$N$개의 데이터를 가진 배열 array에 for문을 이중으로 순회하므로 $N^2$의 시간 복잡도를 가진다.

요약

• 선택 정렬(Selection Sort)이란 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환하는 알고리즘이다.
• 선택 정렬 알고리즘 버블 정렬과 같이 '비교와 교환' 이라는 두 가지 중요한 단계를 포함한다.
  즉, 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교하고, 최솟값을 올바른 위치에 있는 교환한다.
• 선택 정렬 알고리즘의 시간 복잡도는 $O(N^2)$이다.
• 빅 오 표기법에서는 일반적인 카테고리의 알고리즘 속도만을 표기하기 때문에 지수를 제외한 수(상수)는 제외하고 표기한다.
• $O(1)$, $O(logN)$, $O(N)$, $O(N^2)$ 모두 일반적인 빅 오 카테고리 중 하나이다.
• 같은 카테고리에 속한 알고리즘이더라도, 즉 같은 시간 복잡도를 가진 알고리즘이더라도 세부적으로 알고리즘 수행이 필요한 단계 수가 차이날 수 있다. 그리고 이 차이를 알기 위해서는 더 깊은 분석을 해야 한다.