빅오 표기법

빅오 표기법이란, 코드를 서로 비교하고 성능을 비교하기 위한 방법이다. 알고리즘의 성능을 비교하기 위해 만들어진 수학적 기준으로, 최악의 상황을 가정하여 평가한다.
빅오 표기법은, 컴퓨터가 처리해야 하는 연산의 개수를 센다. 따라서 하드웨어의 성능과 관계 없이 같은 결과를 낼 수 있다.

빅오 표기법을 사용하면, 입력 크기가 커질 때, 성능이 어떻게 변화하는가를 파악할 수 있다.

시간 복잡도

특정 숫자 이하의 숫자들을 모두 더하는 방식을 비교하면 다음과 같다.

function addUpTo(n) {
	let total = 0;
	for(let i = 1; i <= n; i++) {
		total += 1;
	}
}

위 함수는 반복문 하나로, N의 곱과 선언 2개로 이루어져 있다. 따라서 위 함수를 O(N + 2)이라고 표현할 수 있다.

function addUpTo(n) {
	return n * (n + 1) / 2;
}

위 함수는 연산이 3개의 상수로 이루어져 있다. 따라서 위 함수는 O(3)이라고 표현할 수 있다.

두 가지 함수 모두 정상적으로 작동하지만, 빅오 표기법으로 판단하면, 아래 방식이 더욱 성능이 좋다고 말할 수 있다.

빅오 표기법 단순화하기

빅오 표기법 통해 성능을 계산할 때는 모든 것들을 전부 일일히 계산한 정확한 값이 아닌, 알고리즘의 대략적인 성능을 판단하기 위한 것이기 때문에 단순화할 수 있다.

따라서 위의 예시도 첫 번째의 경우, O(410n) 혹은 O(2n) 이런 식의 표기법보다 다음과 같이 단순화하여 표기할 수 있다.

Case1. O(n + 10) => O(n)
Case2. O(1000n + 50) => O(n)
Case3. O(n^2 + 5n + 8) => O(n^2)

상수로 계산되는 값
1. 산수(더하기, 빼기, 곱하기 나누기)
2. 변수 선언
3. 인덱스를 사용하여 배열의 요소에 접근하거나 key로 객체의 요소에 접근하는 것

공간 복잡도

공간 복잡도는 사용되는 메모리 공간을 계산한다.

불변 공간

• Boolean
• Number
• undefined
• null

위 값들은 불변 공간이다. 이는 입력의 크기와 상관없이 불변 공간, 즉 일정한 메모리 공간을 차지한다. (1과 1000은 같은 메모리 공간을 차지한다.)

문자열, 배열과 객체 타입은 O(n)의 공간을 필요로 한다.

로그

위에 나온 O(1), O(n), O(n^2) 외에도 O(n log n), O(log n)이 있다.

효율적인 정렬 알고리즘이 이와 관련되어 있다. 재귀도 가끔 로그 공간 복잡도를 가진다.

성능

빅오 표기법에서 가장 성능이 좋은 것은 물론 상수, O(1)이다.