빅오 표기법 (Big O Notation)

빅오 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 표현하는 데 사용되는 수학적 표기법이다. 이 표기법은 입력 데이터 크기(n)가 커질 때 알고리즘 성능이 어떻게 변하는지를 나타내기 위해 사용된다.

시간 복잡도

시간 복잡도는 알고리즘이 주어진 입력을 처리하는 데 걸리는 시간의 상한선을 나타낸다.

시간 복잡도가 낮은 순서대로 알아보자.

1. O(1) - 상수 시간 복잡도. 입력 크기와 무관하게 알고리즘이 일정한 시간 내에 실행된다. 예시로 배열의 첫 번째 원소를 읽는 작업은 O(1)이다.

// O(1) - 상수 시간 복잡도

// 예시: 배열의 첫 번째 원소를 가져오는 함수
function getFirstElement(arr) {
	return arr[0];
}

const arr = [1, 2, 3, 4, 5];
console.log(getFirstElement(arr)) // O(1)

2. O(log n) - 로그 시간 복잡도. 입력 크기가 커질수록 시간이 천천히 증가한다. 예시로 이진 탐색 알고리즘이 이에 해당한다.

// O(log n) - 로그 시간 복잡도

// 정렬된 배열에서 이진 탐색

function binarySearch(arr, target) {
	let low = 0;
    let high = arr.length -1;
    
    while (low <= high) {
    	let mid = Math.floor((low + high) / 2);
        
        if (arr[mid] === target) {
        	return mid;
        } else if (arr[mid] < target) {
        	low = mid + 1;
        } else {
        	high = mid - 1;
        }
    }
    return -1;
}

const arr4 = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(binarySearch(arr4, 6)) // O(log n)

3. O(n) - 선형 시간 복잡도. 입력 크기에 비례하여 실행 시간이 증가한다. 예시로 배열에서 원소를 하나씩 탐색하는 경우이다.

// O(n) - 선형 시간 복잡도

// 배열에서 특정 원소를 찾는 함수

function findElement(arr, target) {
	for (let i = 0; i < arr.length; i++) {
    	if (arr[i] === target) {
        	return i;
        }
    }
    return -1;
}

const arr2 = [1, 2, 3, 4, 5];
console.log(findElement(arr2, 3)) // O(n)

4. O(n log n) - 선형 로그 시간 복잡도. 예시로 병합 정렬이나 퀵 정렬이 이에 해당한다.

//O(n log n) - 선형 로그 시간 복잡도

//병합 정렬 알고리즘

function mergeSort(arr) {
	if (arr.length <= 1) {
    	return arr;
    }
    
    const mid = Math.floor(arr.length / 2);
	const left = mergeSort(arr.slice(0, mid));
	const right = mergeSort(arr.slice(mid));

	return merge(left, right);
}

function merge(left, right) {
	let result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    
    while (leftIndex < left.length && rightIndex < right.length) {
    	if (left[leftIndex] < right[rightIndex]) {
        	result.push(left[leftIndex]);
            leftIndex++;
        } else {
        	result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

const arr5 = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr5)); // O(n log n)

5. O(n^2) - 이차 시간 복잡도. 입력 크기의 제곱에 비례하여 실행 시간이 증가한다. 이중 루프가 있는 경우 주로 발생하며 예시로 버블 정렬 알고리즘이 이에 해당한다.

//O(n^2) - 이차 시간 복잡도

// 버블 정렬 알고리즘

function bubbleSort(arr) {
	let n = arr.length;
    for (let i = 0; i < n; i++) {
    	for (let j = 0; j < n - i - 1; j++) {
        	if (arr[j] > arr[j + 1]) {
            	[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
}

const arr3 = [64, 34, 25, 12, 22, 11, 90];
bubbleSort(arr3);
console.log(arr3); // O(n^2)

공간 복잡도

공간 복잡도는 알고리즘이 실행될 때 필요한 메모리 공간의 상한선을 나타낸다.

1. O(1) - 상수 시간 복잡도. 알고리즘이 입력 크기와 관계없이 일정한 양의 메모리만 사용한다.

// O(1) - 상수 공간 복잡도

// 배열의 합을 구하는 함수

function increment(arr) {
	let sum = 0;
    for (let i = 0; i< arr.length; i++) {
    	sum += arr[i];
    }
    return sum;
}

const arr = [1, 2, 3, 4, 5];
console.log(increment(arr)) // O(1)

이 예제에서는 sum 변수 하나만 사용되므로, 입력 크기와 상관없이 메모리 사용량이 일정하다.

 

2. O(n) - 선형 시간 복잡도. 입력 크기에 비례하여 메모리 사용량이 증가한다.

// O(n) - 선형 공간 복잡도

// 배열을 복사하는 함수

function copyArray(arr) {
	let newArr = [];
    for (let i = 0; i < arr.length; i++) {
    	newArr.push(arr[i]);
    }
    return newArr;
}

const arr2 = [1, 2, 3, 4, 5];
console.log(copyArray(arr2));

빅오 표기법의 주요 특징

빅오 표기법은 일반적으로 최악의 경우 성능을 나타낸다. 예를 들어, 최악의 경우 시간 복잡도는 알고리즘이 처리해야하는 가장 큰 입력에 대해 걸리는 시간을 나타낸다. 또한 빅오 표기법에서는 성능에 미치는 영향이 미미한 상수와 낮은 차수의 항을 무시한다. 예를 들어, O(2n + 3)은 O(n)으로 표현한다.