4장 빅 오로 코드 속도 올리기

빅 오를 사용하면 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 기회가 생긴다.

4-1 버블정렬

정렬 알고리즘 ?: 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 수년간 수십개의 정렬 알고리즘이 개발돼 있다.

정렬되지 않은 배열이 주어졌을 대, 어떻게 오름차순으로 정렬할 수 있을까?에 대한 문제를 해결한다.

배열 정렬의 단계

1. 배열 내에서 연속된 두 항목을 가르킨다. 처음에는 배열의 첫 번째 원소부터 시작해서 처음 두 항목을 가르킨다. 첫 번째 항목과 두 번째 항목을 비교한다.
2. 두 항목의 순서가 뒤바뀌어 있으면 두 항목을 교환한다. 순서가 올바르다면 2단계에서는 아무것도 하지 않는다.
3. 포
4. 배열의 끝까지 또는 이미 정렬된 값까지 1단계부터 3단계를 반복한다. 이것을 배열의 첫 패스스루라 끝났다 라고 한다. 즉, 배열 끝까지 값을 하나하나 가르키며 배열을 통과했다.
5. 두 포인터를 다시 배열의 처음 두 값으로 옮겨서 1단계부터 4단계를 다시 힐행함으로써 새로운 패스스루를 실행한다. 교환이 일어나지 않는 패스스루가 생길 때까지 패스스루를 반복한다. 교환할 항목이 없다는 것은 배열이 정렬됐고 문제를 해결했다는 뜻

4-2 버블 정렬 실제로 해보기

[4, 2, 7, 1, 3] 이라는 배열을 정렬하고 싶다고 가정하자

1. 먼저 4와 2를 비교
2. 순서가 맞지 않으므로 둘을 교환한다 [2, 4, 7, 1, 3]
3. 다음으로 4와 7을 비교한다 [2, 4, 7, 1, 3]
4. 이제 7와 1을 비교한다
5. 순서가 맞지 않으므로 교환한다 [2, 4, 1, 7, 3]
6. 7과 3을 비교한다 [2, 4, 1, 3, 7]
7. 순서가 맞지 않으므로 교환한다. 이제 7은 확실히 배열 내에서 올바른 위치에 있다. 7은 정렬되지 않은 값 중 가장 큰 값이다. 즉, 버블이었고 계속해서 오른쪽으로 옮겼기 때문이다.
8. 두 번째 패스스루를 시작하면서 2와 4를 비교한다
9. 올바른 순서이므로 다음 단계로 넘어가면서 4와 1을 비교한다
10. 순서가 맞지 않으므로 교환한다 [2, 1, 4, 3, 7]
11. 4와 3을 비교한다
12. 순서가 맞지 않으므로 교환한다 [2, 1, 3, 4, 7] 첫 패스스루를 통해 7이 이미 올바른 위치에 있기 때문에 4와 7은 비교할 필요가 없으며 두 번재 패스스루도 끝이났다
13. 두 번째 패스스루에서 교환을 적어도 한 번 수행했으니 다음 패스스루를 수행한다. 2와 1을 비교한다
14. 순서가 맞지 않으니 교환한다 [1, 2, 3, 4, 7]
15. 2와 3을 비교한다. 순서가 올바르닌 교환할 필요가 없다
16. 네 번째 패스스루를 시작한다. 1과 2를 비교한다. 순서가 올바르니 교환할 필요가 없다. 나머지 값은 모두 이미 올바르게 정렬됐으니 네 번째 패스스루를 종료할 수 있다.

4-2-1 버블 정렬 구현

const bubbleSort = (list) => {
	let unsortedUntilIndex = list.lenght - 1;
	let sorted = false;
	
while(!sorted){
	sorted = true;
	for(let i = 0; i < unsortedUntilIndex.length; i++){
		if(list[i] > list[i+1]){
			[list[i], list[i+1]] = [list[i+1], list[i]];
			sorted = false;
		}
	}
	unsortedUntilIndex -= 1;
}
return list;
}

• unsortedUntilIndex 변수는 아직 정렬되지 않은 배열의 가장 오른쪽 인덱스이며 처음 시작할 때 전체 배열이 정렬되지 않은 상태이므로 배열의 마지막 인덱스로 초기값을 설정한다
• sorted 변수는 배열의 정렬 여부를 기록
• while 루프는 한 패스스루에 해당한다. 즉, 한 번의 루프가 한 번의 패스스루이다. 각 패스스루는 정렬이 되어 있다고 가정하고 값을 교환하면 변수를 다시 false로 바꾸는 방식을 취한다. 따라서 교환이 일어나지 않으면 sorted변수가 true로 남아서 배열이 완전히 정렬된 상태임을 알 수 있다.
• for 루프 안에서는 배열 내 모든 값 쌍을 가리킨다. 배열의 첫 인덱스부터 아직 정렬되지 않은 인덱스(unsortedUntilIndex)까지 반복문을 수행한다. for 루프 내에서는 모든 인접 값 쌍을 비교하고 순서가 뒤바뀌어 있으면 교환한다. 교환이 이루어지면 sorted를 false로 바꾼다.
• 각 패스스루가 끝나면 unsortedUntilIndex의 값이 정렬된 상태이니 1을 감소시킨다
• sorted가 true가 되면, 즉 배열이 완전히 정렬되면 while 루프가 종료된다. 이때 정렬된 배열을 반환

4-3 버블 정렬의 효율성

버블 정렬 알고리즘은 두 가지 중요한 단계를 포함한다

• 비교 ?: 어느 쪽이 더 큰지 두 수를 비교한다
• 교환 ?: 정렬하기 위해 두 수를 교환한다

예제의 배열은 원소가 5개의 배열에서 첫 번째 패스스로는 4번, 두 번째는 3번, 세 번째는 2번, 네 번째는 1번의 비교를 했다. 따라서, 4 + 3 + 2 + 1 = 10번의 비교

버블 정렬은 (N - 1) + (N - 2) + (N - 3) … + 1번의 비교를 수행한다.

최악의 시나리오라면 비교할 때 마다 교환을 해야한다. 즉, 시나리오에서는 비교 10번, 교환 10번이 일어나 총 20단계가 필요하다.

• 원소 10개 배열의 최악의 시나리오에서는 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45번의 비교와 45번의 교환이 일어나므로 총 90단계이다.
• 원소 20개는 19 + … 1 = 190번의 비교와 190번의 교환이므로 총 380단계이다.

즉, 버블 정렬은 원속가 N개일 때 대략 N² 만큼 늘어난다. 따라서 빅 오로 나타내면 버블 정렬의 효율성은 O(N²)이다. 이를 이차 시간이라고도 부른다

O(N²)은 데이터가 증가할 때 단계 수가 급격히 늘어나므로 비교적 비효율적인 알고리즘으로 간주 된다.

4-4 이차 문제

배열에 숫자가 중복으로 들어 있으면 가장 먼저 떠오르는 방법 중 하나가 중첩 루프다.

const hasDuplicateValue = (array) => {
	for(let i = 0; i < array.length; i++) {
		for(let j = 0; j < array.length; j++) {
			if(i !== j && array[i] === array[j]) {
				return true;
			}
		}
	}
	return false
}

확인할 배열에 중복값이 없는 것이 최악의 시나리오다. 이때 바깥 루프는 배열을 전부 살펴보기 위해 N번을 순회해야 하고, 순회할 때마다 안쪽 루프는 다시 N번을 순회해야 한다. 즉, O(N²)인 알고리즘이다.

루프 내에 다른 루프를 중첩하는 알고리즘이라면 대부분 O(N²)이다. (항상은 아니다) O(N²)은 상대적으로 느린 알고리즘으로 간주되기에, 시간을 들여 더 빠른 대안은 없을지 깊이 생각해 보는 것이 좋다.

4-5 선형 해결법

다음처럼 중첩 루프를 쓰지 않는 hasDuplicateValue 함수를 구현해 볼 수 있다

const hasDuplicateValue = (array) => {
	let existingNumbers = [];
	for(let i = 0; i < array.length; i++) {
		if(existingNumbers[array[i]] === 1) {
			return true;
		}
		else{
			existingNumbers[array[i]] = 1;
		}
	}
return false;
}

• existingNumbers라는 빈 배열을 생성한다
• 반복문에선 배열의 원소 값을 existingNumber의 인덱스로 하여 해당 인덱스에 임의의 값(예제에서는 1)을 집어넣는다. 이때, 조건식으로 해당 인덱스에 이미 1이 있는지 확인하여, 없다면 집어넣고, 있다면 중복 값이 있다는 뜻이므로 true를 리턴한다. true가 반환되지 않고 반복문이 끝났다면 중복 값이 없다는 뜻이므로 false를 반환한다.
• hasDuplicateValue([0, 2, 3, 2])을 실행한다고 가정하면, existingNumber는 0, 2, 3의 루프를 돌며 [1, undefined, 1, 1]이 된다.
• 그리고 마지막 원소인 2의 루프를 돌 때, existingNumber[2]이 undefined가 아닌 1이므로, if(existingNumber[array[i]] === 1)이 참이 돼 return true가 실행된다.

이 알고리즘의 단계 중 주요 유형은 existingNumber에서 해당 인덱스의 값이 1인지 확인하는 것이다. 배열에 중복 값이 없을 때가 최악의 시나리오이고, 이때 N번의 단계를 거치게 된다. 즉, O(N)인 알고리즘이다.

이 방식은 첫 번째 방식보다 메모리를 더 소비한다. 19장에서 상세히 다룬다.

4-6 마무리

빅 오 표기법을 명확히 이해하면 느린 코드를 식별해 내고 두 경쟁 알고리즘 중 더 빠른 알고리즘을 분명하게 골라낼 수 있다.