빅오(Big-O) 표기법

---

컴퓨터 과학(Computer Science) 에서 알고리즘은 어떠한 문제를 해결하기 위한 방법이고, 어떠한 문제를 해결 하기 위한 방법은 다양하기 때문에 방법(알고리즘) 간에 효율성을 비교하기 위해 빅오(big-O) 표기법을 보통 가장 많이 사용한다.

알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다. 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다. (시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)

출처: https://noahlogs.tistory.com/27 [인생의 로그캣]

빅오(Big-O)?

• 알고리즘의 성능을 수학적으로 표기해주는 표기법.
• 시간 & 공간 복잡도 표현 가능
• 알고리즘의 실제 러닝타임을 표시하는거라기 보다 데이터나 사용자의 등가율에 따른 알고리즘의 성능을 예측하는게 목표
• 상수와 같은 숫자들은 모두 1이된다.

가장 기본적으로 알아두어야할 빅오표기법의 예

예시1: O(1)

F(int[] n) {
	return (n[0] == 0)? true:false;
}

• 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
• 파라미터로 받는 배열의 크기의 상관없이 언제나 일정한 속도로 결과를 반환
• 이러한 "알고리즘을 O(1)의 시간복잡도를 가진다" 라고 한다.

예시2: O(n)

F(int[] n) {
	for i = 0 to n.length
		print i
}

• 입력데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘
• n개의 데이터를 받으면, n이 하나 늘어날때마다 처리가 하나씩 늘어나서 n의 크기만큼 처리시간이 걸리게 된다.

예시3: O(n^2)

F(int[] n) {
	for i = 0 to n.length
		for j = 0 to n.length
			print i + j;
}

• n으로 for문으로 돌리면서 그 안에서 또 n으로 루프를 돌릴때 n^2가 된다

예시: O(nm)

F(int[] n, int[] m) {
	for i = 0 to n.length
		for j = 0 to m.length
			print i + j;
}

참고 https://youtu.be/6Iq5iMCVsXA