Ch.05 빅 오를 사용하거나 사용하지 않는 코드 최적화 (도서 요약 "누구나 자료구조와 알고리즘")
빅 오는 알고리즘을 서로 비교하는데 훌륭한 도구다. 하지만 빅 오 표기법에서는 한 알고리즘이 다른 알고리즘보다 훨씬 빠른 경우에도 두 알고리즘을 정확히 똑같은 방식으로 표현하기도 하는 한계가 있다. 따라서 효율성이 같아 보이는 두 알고리즘을 구별해 내서 더 빠른 알고리즘을 고르는 별도의 방법이 있다.
5. 1 선택 정렬
'선택 정렬(selection sort)'은 또 다른 정렬 알고리즘이다(앞에서 본 '버블 알고리즘'은 O(N²)이었다).
선택 정렬은 다음과 같은 단계를 따른다.
(1) 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 확인한다.
(2) 한 셀씩 이동하면서 현재까지 가장 작은 값이 있는 인덱스를 변수에 저장한다.
(3) 현재 최솟값보다 작은 값이 들어 있는 셀을 만나면 변수가 새로운 인덱스를 가리킨다.
(4) 끝까지 비교했으면, 기록한 인덱스의 값과 패스스루를 시작했을 때의 왼쪽 값을 교환한다.
(5) 첫 번째 패스스루가 끝났으면, 해당 패스스루에서 가장 작은 값이 가장 왼쪽으로 이동되었을 것이다.
(6) 두 번째, 세 번째 ... 패스스루에서 위 단계를 반복한다.
5. 2 선택 정렬 실제로 해보기
선택 정렬을 자바 코드로 나타내면 다음과 같다.
public void selectionSort(int[] arr) {
// 배열의 원소를 하나씩 비교하며 최솟값 인덱스를 검색
for(int i=0; i<arr.length-1; i++) {
int lowestNumberIndex = i;
for(int j=i+1; j<arr.length; j++) {
if(arr[j] < arr[lowestNumberIndex]) {
lowestNumberIndex = j;
}
}
// 최솟값 인덱스의 값과 첫번째 값을 교환
if(lowestNumberIndex != i) {
int temp = arr[i];
arr[i] = arr[lowestNumberIndex];
arr[lowestNumberIndex] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
각 패스스루를 나타내는 루프를 시작한다. 루프는 변수 i를 사용해 arr 배열의 각 값을 가리키며, 끝에서 두 번째 값까지 살펴본다. 마지막 값을 시작하기 전에 이미 배열이 완전히 정렬되므로 마지막 값은 보지 않아도 된다(i<arr.length-1).
for(int i=0; i<arr.length-1; i++) {
현재까지의 최솟값이 들어 있는 인덱스를 저장한다.
첫 패스스루를 시작할 때는 0, 두 번째 패스스루를 시작할 때는 1일 것이다.
int lowestNumberIndex = i;
각 패스스루에서는 배열의 나머지 값들을 확인해 현재 최솟값보다 더 작은 값이 있는지 알아본다.
for(int j=i+1; j<arr.length; j++) {
실제로 더 작은 값을 찾으면 이 값의 인덱스를 lowestNumberIndex에 저장한다. 이렇게 안쪽 루프가 종료되는 시점에 이번 패스스루에서 가장 작은 수의 인덱스가 결정된다.
if(arr[j] < arr[lowestNumberIndex]) {
lowestNumberIndex = j;
}
패스스루의 최솟값이 이미 올바른 위치에 있으면(이미 시작 지점( i )에 있다면) 아무것도 하지 않아도 된다. 하지만 최솟값이 올바른 위치에 있지 않으면 교환을 해야 한다.
if(lowestNumberIndex != i) {
int temp = arr[i];
arr[i] = arr[lowestNumberIndex];
arr[lowestNumberIndex] = temp;
}5. 3 선택 정렬의 효율성
선택 정렬은 '비교'와 '교환'이라는 두 종류의 단계를 가진다. 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교하고, 최솟값을 올바른 위치에 있는 수와 교환한다.
만약 5개의 원소를 가진 배열이라면, 총 10번의 '비교'를 해야 한다.
총 4 + 3 + 2 + 1 = 10번의 비교다.
즉, 원소 N개가 있을 때 (N - 1) + (N - 2) + (N - 3) .... + 1번의 비교다.
이와 달리 '교환'은 한 패스스루 당 최대 한 번 일어난다. 각 패스스루마다 최솟값이 이미 올바른 위치에 있느냐에 따라 교환을 안 하거나 교환을 한 번 하기 때문이다. 최악의 시나리오에서는 모든 원소마다 교환하는 버블정렬과 달리, 비교할 때마다 교환을 한 번만 하면 된다.
선택 정렬이 버블 정렬보다 반 정도 적어 두 배 더 빠르다.
5. 4 상수 무시하기
하지만 빅 오 표기법에서는 선택 정렬과 버블 정렬을 정확히 같은 방식으로 표현한다.
빅 오 표기법은 데이터 원소 N개일 때 얼마나 많은 단계 수가 필요한가라는 질문에 대한 답이다. 선택 정렬은 데이터 원소가 N개일 때 대략 N² / 2단계가 필요하지만, 빅 오로 표현하면 버블 정렬과 똑같이 O(N²)이다.
그 이유는 빅 오의 규칙 때문이다.
빅 오 표기법은 상수를 무시한다.
빅 오 표기법은 지수가 아닌 수는 포함하지 않기 때문에 표현식에서 " / 2"와 같은 수는 그냥 버린다. 따라서 선택정렬 알고리즘에는 N² / 2단계가 필요했지만 " / 2"를 버리고 효율성을 O(N²)으로 표현한다.
다른 예론,
* N² + 10단계가 필요한 알고리즘은 지수가 아닌 10을 버리고 O(N²)으로 표현한다.
* 2N²가 필요한 알고리즘은 2를 버리고 O(N²)으로 표현한다.
* O(N) 보다 100배나 느린 O(100N)도 100을 버리고 O(N²)으로 표현한다.
이렇게 표현하는 이유는 무엇인가?
5. 5 빅 오 카테고리
빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.
만약 단독 주택과 고층 건물을 비교한다면 굳이 각각 몇 층인지 언급할 이유가 없다. 하나는 '집'이라 부르고 나머지 하나는 '고층 건물'이라고 부르는 편이 낫다. 일반적인 카테고리로만 분류해도 현저한 차이를 나타내기 충분하다.
알고리즘의 효율성도 마찬가지이다. 빅 오 표기법의 본질은 데이터가 늘어날 때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지에 있다. O(N)은 직선 성장(straight growth)인 반면, O(N²)은 지수 성장(exponential growth)의 하나로 둘은 완전히 다른 카테고리이다. O(N)에 어떤 수를 곱하든 언젠가 결국 O(N²)이 더 느려지는 순간이 온다.
위 그래프에서 나타나듯, N에 여러 상수를 곱해도 결국 O(N²)이 느리다. 그래서 O(N)이 실제로 O(2N)이든, O(N / 4)이든, O(100N)이든 중요하지 않다. 따라서 빅 오에선 일반적인 카테고리로 분류하는 것으로 충분하다. O(2N)도 O(N) 카테고리에 속한다고 말하는 편이 훨씬 낫다.
결론은 O(1), O(logN), O(N), O(N²)은 서로 차이가 큰 빅 오 카테고리다. 지수가 아닌 수로 단계 수를 곱하거나 나눈다고 카테코리가 바뀌지 않는다는 점이다.
물론 두 알고리즘이 같은 카테고리에 속하더라도 서로 처리 속도가 다를 수 있다. 버블 정렬과 선택 정렬은 둘 다 O(N²)이지만 속도 차이는 두 배이다. 때문에 같은 카테고리에 속하는 알고리즘 간의 비교는 빅 오로는 불충분하다.
5. 6 마무리
두 알고리즘의 효율성을 비교할 때 고려해야 할 중요한 요인이 있다. 지금까지는 알고리즘이 최악의 시나리오에서 얼마나 빠른가에 초점을 맞췄다.
그러나 최악의 시나리오는 항상 일어나지 않는다. 대체로는 평균 시나리오다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.