알고리즘의 성능 분석

성능 분석

실행되는 빈도수를 계산한 시간 복잡도를 사용
```
  for (i=0; i<n; i++)
      x = x + y;
```
– 위 코드에서 x = x + y라인은 n번 수행

점근적 표기

알고리즘의 수행 시간을 표기하기 위해 필수적인 부분에 집중하고 불필요한 부분은 무시한다.

낮은 차수에 어떤 수가 붙더라도 제일 높은 차수의 증가폭이 가장 크다
필수적인 부분: 높은 차수 / 불필요: 낮은 차수
종류: O-표기법, Ω-표기법, θ-표기법
Time Complex: $\frac{1}{n} < 1 < log n < \sqrt n < nlogn < n^2$

Big-O 표기법

정의

$O(g(n)) = f(n)$일 때 모든 n ≥ $n_0$에 대해 $0 ≤ f(n) ≤ g(n)$인 양의 상수 c와 $n_0$가 존재한다.

f(n)은 나의 알고리즘의 시간 효율성
g(n) 알고리즘의 최악의 시간 효율

특징

점근적인 상한선을 의미함
주어진 알고리즘이 아무리 효율성이 나빠도 g(n)보다 좋거나 같다.
데이터 입력값의 크기가 중요하므로 상수항은 무시한다.
최고차항을 제외한 낮은 차항은 무시한다.

Big-θ 표기법

정의

$θ(g(n)) = f(n)$일 때 모든 n ≥ $n_0$에 대해 $0 ≤ c_1g(n)≤ f(n) ≤ c_2g(n)$이 성립하는 양의 상수 $c_1$, $c_2$와 $n_0$가 존재한다.

특징

평균적인 경우를 의미함
big-O, big-Omega 표기법과 같다.
– 수행시간이 O(n), Ω(n)이면 θ(n)이다.

Big-Ω 표기법

정의

$Ω(g(n)) = f(n)$일 때 모든 n ≥ $n_0$에 대해 $cg(n) ≤ f(n)$이 성립하는 양의 상수 $n_0$가 존재한다.

특징

최선의 경우를 의미한다.
주어진 알고리즘이 아무리 좋아도 g(n)과 같거나 나쁘다.

예시

1. $7n^5 - 3n +2$ 을 Big-O, Big-Ω로 표현해보자

– Big-O 표기

$7n^5 - 3n +2 < 2^n (n>26.4271)$
$∴ O(2^n)$

– Big-Ω 표기

$2^{log{^2}n} > n^2 (n>4)$
$∴ Ω(n^2)$

2. $2^{log{^2}n}$ 을 Big-O, Big-Ω로 표현해보자

– Big-O 표기

$2^{log{^2}n} < 2^n (n>e^{-2W(log2/2)^{-1}})$
$∴ O(2^n)$

– Big-Ω 표기

$2^{log{^2}n} > n^2 (n>4)$
$∴ Ω(n^2)$

추가적인 내용

1. little o 표기

모든 양의 상수 c>0에 대해 그리고 모든 $n ≥ n_0$에 대해 $0 ≤ f(n) ≤ cg(n)$인 양의 상수 $n_0$가 존재

2. little w 표기

모든 양의 상수 c>0에 대해 그리고 모든 $n ≥ n_0$에 대해 $0 ≤ cg(n) ≤ f(n)$인 양의 상수 $n_0$가 존재

30 Nov 2022

« 연관관계 매핑

Greedy 알고리즘 »

homebdy Follow 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람. 개발에 이제 막 발 담근 사람.

Categories