계산 복잡도 - 빅오 표기법(big O)

직접 구현하지 않고서도 알고리즘의 효율성을 따져보는 기법으로 알고리즘의 복잡도 분석이 있다.

이 방법에는 2가지 방법이 있는데 알고리즘의 수행시간을 분석하는 시간 복잡도 , 알고리즘이 사용하는 기억공간을 분석 하는

공간 복잡도가 있다.

알고리즘 복잡도를 이야기할 떄는 대게 시간 복잡도를 뜻하며 시간 복잡도의 표시는 빅오 표기법(big-oh notation)으로 한다.

빅오 표기법(Big-Oh Notation)

---

1. 시간 복잡도 표기법

시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시함.

O(3n+2) = O(3n) = O(n)이 된다.

2. 수학적 정의

모든 N >= N0 에 대해서 f(N) <= cg(N)이 성립하는 양의 상수 c와 N0이 존재하면, f(N) = O(g(N))이다.

3. 빅오 표기

T(n)=n^2 + n + 1

여기서 n의 값이 클수록 차수가 가장 큰n^2 항이 전체의 값에 큰 영향을 주는데 이렇게 가장 큰 영향을 미치는 항만

고려하여 T(n)을 빅오 표기법화하면 O(n^2)이다.

4.시간 복잡도와 의미

O(c) - 상수값을 갖는 알고리즘 , 가장 빠른 수행 속도

O(logn) - 밑이 2인 로그 함수와 같은 수행속도를 보인다는 의미 , n값이 증가할수록 수행속도가 포물선을 그리면서 한쪽으로 

수렴해 많은 샘플 데이터를 처리할 때 우수한 성능늘 보장.

O(n) - 선형 함수 형태, 샘플 데이터에 정비례해서 수행시간이 걸림.

O(n^2) -  n의 제곱으로 수행속도가 떨어짐 , 이런 알고리즘은 n이 적을 경우에 사용.

O(n^3) - n의 세제곱.

O(2^n) 익스포넨셜 함수. 이렇게 만들어서 쓰는 알고리즘은 거의 없다.

빅오 시간 복잡도 그래프

 

함수의 분류

---

프로그램에서 입력의 크기가 작으면 알고리즘의 효율과는 상관없이 함수의 수행은 빨리 끝나게 된다.

하지만 문제가 되는 것은 입력의 크기가 아주 클 때인데 알고리즘의 수행시간을 분석할 때는 항상 입력 크기가

충분히 클 때에 대해 분석을 한다. 점근적 분석이다.

1. 점근적 상한(asumptotic upper bound)

n > n0인 모든 n에 대해 f(n) < c g (n)을 만족하는 2개의 양의 상수 c, n0 이 존재하면 f(n)=O(g(n)) 이라 함.

점근적 상한

2. 점근적 하한 - 오메가 표기법

 Ω(g(n)) = {f(n) : n≥ n₁인 모든 n에 대해 0 ≤  cg(n) ≤f(n)를 만족하는 양수 상수 c와n₁가 존재.

점근적 하한

3. 점근적 상한과 하한 - 세타 표기법

Θ(g(n)) = {f(n) : n≥ n₁인 모든 n에 대해 0 ≤  c₁g(n) ≤ f(n) ≤ c₂g(n)를 만족하는 양수 상수 c₁,c₂와n₁가 존재.

점근적 하한과 상한을 동시에 갖는다. 

Big O 표기법이 제일 많이 쓰이고.. 제일 중요하다 !