1. 정의

빅오 표기법은 알고리즘의 효율성을 알기 쉽게 표현해주는 표기법이다. 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다. 기본 연산의 횟수가 적은 알고리즘이 효율성이 더 좋다고 판단할 수 있다. 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용한다.

여기서 시간 복잡도와 공간 복잡도는 각각 알고리즘의 시간 효율성과 공간(메모리) 효율성을 의미한다.

시간 복잡도 = 상수함수 < 로그함수(이진트리) < 선형함수 < 다항함수 < 지수함수

Ex)

// O(n)
function example(n) {
	for(var i = 0; i < n; i++){
		console.log(i);
	}
}

// O(n^2)
function example(n) {
	for(var i = 0; i < n; i++){
		console.log(i);
		for(var j = 0; j < n; j++) {
			console.log(j)
		}
	}
}

2. 빅오 표기법 규칙

1) 계수 법칙(상수 무시)

빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고, 알고리즘의 효율성 또한 입력값의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.
ex) 0(2n) => O(n)

2) 합의 법칙

합의 법칙은 결괏값인 시간 복잡도가 두 개의 다른 시간 복잡도의 합이라면 결괏값인 빅오 표기법 역시 두 개의 다른 빅오 표기법의 합이라는 것을 의미한다.

3) 곱의 법칙

곱의 법칙은 두 개의 다른 시간 복잡도를 곱할 때 빅오 표기법 역시 곱해진다는 것을 의미한다.

4) 전이 법칙

전이 법칙은 동일한 시간 복잡도는 동일한 빅오 표기법을 지님을 나타내기 위한 간단한 방법이다.

5) 다항 법칙

직관적으로 다항 법칙은 다항 시간 복잡도가 동일한 다항 차수의 빅오 표기법을 지님을 나타낸다.
ex) f(n)이 k차 다항식이면 f(n)은 O(n^7)

2. 그래서 빅오 표현식이 왜 중요할까?

알고리즘 효율성의 표현법에서 빠르다와 느리다의 정의는 시간으로 표현하는 것이 아니다. 각 하드웨어의 스펙에 따라서 결과가 다를 가능성이 있기 때문에 알고리즘 효율은 '완료까지 걸리는 절차의 수'로 결정된다. 쉽게 얘기해서 알고리즘이 결과를 도출하는 과정의 절차가 50개인 알고리즘보다 5개인 알고리즘이 더 빠르다는 뜻이다.

Big O를 이해하면 알고리즘 분석을 빠르게 할 수 있고, 언제 무엇을 쓸지 빠르게 결정할 수 있다. 또한 자신의 코드를 평가하는 지표로 사용된다. Big O는 러프하게 어떻게 이 함수가 작동하는지 input 사이즈에 따라서 어떻게 절차가 바뀌는지에 관점을 맞춘다.

선형 검색 알고리즘 : 선형 검색은 한개씩 검색을 하는 방식 따라서 데이터가 10개이면 아이템을 찾는 스텝이 10개인 경우이다. 선형 검색 알고리즘은 input size가 N개라면 N개의 절차가 필요하다는 의미다. 즉, 선형검색의 시간 복잡도는 O(n)이다. 이런 표현식이 BigO표현식이다. 시간 복잡도를 빠르게 설명할 수 있다.