빅 오 (Big - O) 표기법

-빅 오 표기법이란?-

알고리즘의 성능을 수학적으로 표기해주는 표기법

이것으로 알고리즘의 시간과 공간 복잡도를 표현할 수 있음

데이터나 사용자에 증가율에 따른 알고리즘의 성능을 예측하는 것이 목표이다.

f(n) = O(g(n)) 일때

f(x) ≤ c(상수) x g(x)

f(x) = 2x^2 + 3 일 때 g(x) = x^2

f(x) = O(g(x))?? (그러니까 O안에 어떤 숫자가 들어가야 f(x)와 g(x)가 같아지는지 증명하라는 문제)

f(x)       ≤  c x g(x) 가 참이되어야 하므로

2x^2+3 ≤  c x (x^2) 가 되어야 한다.

그렇다면 c와 x에다가 무슨 값을 넣어야 위 공식이 성립이 될까?

표를 만들어서 값을 하나씩 대입해보자.

좌항계산	우항계산	결과	x의 값 (대입한것)	c의 값  (대입한것)
2x^2+3	x^2	좌항이 크다.	- (궂이 x의 값을 넣지 않아도 좌항과 우항의 대소 구별이 가능함)	1
2x^2+3	2x^2	좌항이 크다.	- (궂이 x의 값을 넣지 않아도 좌항과 우항의 대소 구별이 가능함)	2
7	5	좌항이 크다.	1	3
8	12	우항이 크다.	2	3

결과적으로 x의 값에 2을 넣고, c의 값에 3을 넣었을 때 우항이 좌항보다 커진다는 사실을 알 수 있다.

결과적으로  c = 3 and x ≥ 2 일때 ,f(x) = O(g(x)) 는 참이 된다. 

출처

https://www.youtube.com/watch?v=Chcl71vEkRg