빅 오 표기법을 이용한 성능 향상
빅 오 표기법이란 알고리즘 평가 단계를 표기하는 방법이다. 여러가지 알고리즘을 비교 검사하여 보다 효율적인 방법을 찾아 프로그램의 효율을 높일 수 있다.
중복 검사 알고리즘
O(N²) 알고리즘
function hasDuplicatedValue1(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (i != j && array[i] === array[j]) {
console.log('true');
return true;
}
}
}
console.log('false');
return false;
}
const array = [1, 2, 3, 4, 5, 6, 6];
hasDuplicatedValue(array);예를 들어 배열의 중복된 값을 검사하는 알고리즘을 검사한다고 생각해 보자. 해당 알고리즘을 빅 오 표기법으로 표기한 결과는 O(N²)이다. 이를 그래프로 그리면 다음과 같다.
위 그래프를 보면 이 알고리즘이 얼마나 비효율적 인지를 알 수 있다. 이처럼 이중 for문이 사용되는 알고리즘의 경우 위 그래프와 같이 그려지기 때문에 대체로 이중 for문을 사용한 알고리즘은 비효율적이라고 할 수 있다.
O(N) 알고리즘
빅 오 표기법으로 해당 알고리즘이 비효율적이라는 것을 발견하면 이를 대체할 수 있는 방법을 생각하는 것이 좋다. 물론 이를 대체할 수 있는 방법이 없을 수도 있다. 위 알고리즘의 경우 이중 for문을 사용하지 않고 O(N)으로 해결할 수 있는 방법이 있기 때문에 알고리즘을 다음과 같이 수정할 수 있다.
function hasDuplicatedValue2(array) {
const existNumber = new Array(100);
existNumber.fill(0);
for (let i = 0; i < array.length; i++) {
if (existNumber[array[i]] === 0) {
existNumber[array[i]] = 1;
} else {
console.log('true');
return true;
}
}
console.log('false');
return false;
}
const array2 = [1, 2, 3, 4, 5, 6, 6];
hasDuplicatedValue2(array2);
이처럼 O(N²)과 O(N)을 그래프로 나타내면 해당 알고리즘이 효율면에서 얼마나 차이가 나는지를 알 수 있다.
(참고) 2N과 N²의 차이
2N
for (let i = 0; i < array.length; i++) {
...
}
for (let j = 0; j < array.length; j++) {
...
}N²
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
...
}
}
빅 오 표기법을 활용하는 방법
위와 같이 중첩 for문을 사용한 알고리즘 O(N²)과 사용하지 않은 알고리즘 O(N)은 확연하게 효율면에서 차이가 난다는 것을 한 눈으로 봐도 알 수 있다. 하지만 빅 오 표기법의 지수를 무시하는 특성상 O(N² / 2)를 O(N²)로 표기하며 O(100N)도 O(N)로 표기한다. 확연하게 차이가 나는 알고리즘임에도 불구하고 빅 오 표기법을 사용하면 차이를 두지 않는다. 그러나 빅 오 표기법으로는 같은 표기법을 사용하더라도 분명히 효율성의 차이가 나기 때문에 이를 비교하여 알고리즘을 선택할 수 있어야 한다.
같은 분류의 알고리즘 비교
같은 분류의 알고리즘이란 같은 지수를 가지고 있어 빅 오 표기법으로는 똑같이 표기되는 것을 말한다. 정렬하는 알고리즘인 버블 정렬과 선택 정렬을 비교하여 빅 오 표기법이 같은 알고리즘(O(N))이라도 보다 효율적인 알고리즘을 선택하는 방법을 배워두자.
버블 정렬
버블 정렬이란 배열의 요소를 하나씩 비교하며 큰 숫자를 오른쪽으로 이동시키는 정렬 알고리즘이다.
- 첫 번째와 두 번째를 비교한다.
- 더 큰 수를 오른쪽으로 이동시킨다.
- 두 번째와 세번째를 비교하고 더 큰 수를 오른쪽으로 이동시킨다.
- 마지막 요소를 비교하면 가장 큰 수가 오른쪽으로 이동해 있다.
- 정렬된 마지막 요소를 제외하고 다시 사이클을 반복한다.
- 첫 번째 요소가 정렬되면 종료한다.
Javascript
// 버블 정렬 (오름차순)
function AscBubbleSort(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
let temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
console.log('array', array);
return array;
}
// 버블 정렬 (내림차순)
function DescBubbleSort(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length - 1; j++) {
if (array[j] < array[j + 1]) {
let temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
console.log('array', array);
return array;
}
const array = [5, 4, 3, 2, 1];
AscBubbleSort(array);
DescBubbleSort(array);Go
package main
import "fmt"
// 버블 정렬 (오름차순)
func AscBubbleSort(array []int) []int {
for i := 0; i < len(array)-1; i++ {
for j := 0; j < len(array)-1; j++ {
if array[j] > array[j+1] {
array[j], array[j+1] = array[j+1], array[j]
}
}
}
return array
}
// 버블 정렬 (내림차순)
func DescBubbleSort(array []int) []int {
for i := 0; i < len(array)-1; i++ {
for j := 0; j < len(array)-1; j++ {
if array[j] < array[j+1] {
array[j], array[j+1] = array[j+1], array[j]
}
}
}
return array
}
// 버블 정렬 (오름차순) 2
func AscBubbleSort2(array []int) []int {
swapped := true
for swapped {
swapped = false
for i := 0; i < len(array)-1; i++ {
if array[i] > array[i+1] {
array[i], array[i+1] = array[i+1], array[i]
swapped = true
}
}
}
return array
}
func main() {
array := []int{5, 4, 3, 2, 1, 0}
fmt.Println(AscBubbleSort(array))
fmt.Println(DescBubbleSort(array))
fmt.Println(AscBubbleSort2(array))
}
버블 정렬의 알고리즘의 최악의 시나리오를 정리하면 다음과 같다.
| 비교 | 교환 | |
| 1cycle | 4 | 4 |
| 2cycle | 3 | 3 |
| 3cycle | 2 | 2 |
| 4cycle | 1 | 1 |
버블 정렬 알고리즘은 O(N²)의 효율성과 비교했을 때 거의 비슷하다고 할 수 있다. 즉, 해당 알고리즘이 효율적이지 못 하다는 것을 알 수 있다. 정렬 알고리즘은 어떻게든 이중 for문을 사용할 수 밖에 없다. 그럼에도 불구하고 우리는 효육적으로 프로그램을 가동하기 위해 보다 나은 알고리즘을 생각해야만 한다. 대표적이 예로 선택 정렬이 있다.
| 원소 N개 | 최대 단계수 | N² |
| 5 | 20 | 25 |
| 10 | 90 | 100 |
| 20 | 380 | 400 |
| 40 | 1560 | 1600 |
| 80 | 6320 | 6400 |
선택 정렬
선택 정렬이란 최소값을 검색하고 한번만 이동하는 정열 알고리즘이다.
- 주어진 배열 중에서 최소값을 찾는다.
- 첫번째 값과 최소값의 위치를 교환한다.
- 첫번째 값을 뺀 나머지 배열을 같은 방법으로 교환한다.
- 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
Javascript
// 선택 정렬 (오름차순)
function AscSelectedSort(array) {
for (let i = 0; i < array.length-1; i++) {
let minIndex = i;
for (let j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) {
let temp = array[j];
array[j] = array[minIndex];
array[minIndex] = temp;
}
}
}
console.log('array', array);
return array
}
const array1 = [5, 4, 3, 2, 1, 0];
AscSelectedSort(array1);
// 선택 정렬 (내림차순)
function DescSelectedSort(array) {
for (let i = 0; i < array.length-1; i++) {
let minIndex = i;
for (let j = i; j < array.length; j++) {
if (array[j] > array[minIndex]) {
let temp = array[j];
array[j] = array[minIndex];
array[minIndex] = temp;
}
}
}
console.log('array', array);
return array
}
const array2 = [0, 1, 2, 3, 4, 5];
DescSelectedSort(array2);Go
func selectedSort(array []int) []int {
count := 0
for i := 0; i < len(array)-1; i++ {
minIndex := i
for j := i; j < len(array); j++ {
if array[j] < array[minIndex] {
minIndex = j
count++
}
}
array[i], array[minIndex] = array[minIndex], array[i]
}
fmt.Println(array)
fmt.Println(count)
return array 버블 정렬과 선택 정렬 비교하기
| 원소 개수 | 버블 정렬 최대 단계 수 | 선택정렬 최대 단계 수 |
| 5 | 20 | 14(10번 비교 + 4번 교환) |
| 10 | 90 | 54(45번 비교 + 9번 교환) |
| 20 | 380 | 199(180번 비교 + 19번 교환) |
| 40 | 1560 | 819(780번 비교 + 39번 교환) |
| 80 | 6320 | 3238(3160번 비교 + 79번 교환) |
버블 정렬과 선택 정렬 모두 빅 오 표기법으로 나타내면 O(N)이지만 두 알고리즘을 정확히 비교하면 위 표처럼 확연하게 차이가 있다는 것을 알 수 있다. 이처럼 빅 오 표기법은 서로 다른 분류라면 쉽게 비교할 수 있지만 같은 분류의 알고리즘이라면 보다 효율적인 알고리즘을 선택할 수 있어야한다.
