반응형
알고리즘 : 입력을 통해서 원하는 출력이 나오도록 처리하는 방법
알고리즘을 만드는 데 필요한 자원들이 있음(시간, 컴퓨터 cpu, 메모리, 통신망대역폭 등)
여기서는 시간만 필요한 자원이라고 생각하기로 함
시간에 대해서 분석
1. 최악으로 걸리는 시간
2. 평균적으로 걸리는 시간
점근적 증가율=
변수의 크기가 충분히 큰 경우, 변수가 커짐에 따라 함수가 증가하는 비율
충분히 크다는 의미 =
모든 n >= n0에 대하여 ~인 n0가 존재한다 = 충분히 큰 n에 대해서는 ~이다
표기법의 수학적 정의
O(g(n)) = {f(n) | ∃c >0, n0 > 0 s.t. ∀n >= n0, f(n) <= cg(n)}
O(g(n)) = {f(n) | 모든 n >= n0에 대하여 f(n) <= cg(n)인 양의 상수 c와 n0가 존재한다}
O(g(n)) = {f(n) | 충분히 큰 모든 n에 대하여 f(n) <= cg(n)인 양의 상수 c가 존재한다}
점근적 표기방법
1. O - 표기법 :
O(f(n)) = 점근적 증가율이 f(n)을 넘지 않는 모든 함수들의 집합
2. Ω- 표기법
Ω(f(n)) = 점근적 증가율이 적어도 f(n)이 되는 모든 함수들의 집합
3. Θ - 표기법
Θ(f(n)) = 점근적 증가율이 f(n)과 일치하는 모든 함수들의 집합
4. o - 표기법
o(f(n)) = 점근적 증가율이 f(n)보다 더 작은 모든 함수들의 집합
5. w - 표기법
w(f(n)) = 점근적 증가율이 f(n)보다 더 큰 모든 함수들의 집합
반응형