# 접근적 표기 분석 ## 목차 --- 1. 무엇? 2. 종류? 3. 분석 예 ## 1. 무엇? --- 좋은 알고리즘 여부를 평가하기 위한 방법. 데이터의 입력 크기(n)가 충분히 큰 경우를 기준함. $$ \lim_{n\to \infty} f(n) $$ ## 2. 종류? --- | 기호 | 발음 | 의미 | |:-----:|:----:|:---| | 𝜪(~) | 오 | 최악의 경우, ~까지 걸림 | | 𝜴(~) | 오메가 | 최적의 경우, ~에 처리 | | 𝜭(~) | 세타 | 최악과 최적 모두 ~ 소요 |  ## 3. 분석 예 --- ### 코드 A ``` int foo (int A[], int n) { int sum = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { sum = sum + A[i] * A[j]; } } return sum; } ``` n이 충분히 큰 경우, - 𝜪(n^2). 최대 n^2번 수행. - 𝜴(n^2). 최소 n^2번 수행. - 𝜭(n^2). 빅오(𝜪)와 오메가(𝜴)가 서로 같기 때문. ### 코드 B ``` int bar(int A[], int n) { int sum = 0; if (n % 2 == 0) { // 짝수 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { sum = sum + A[i]*A[j]; } } } else { // 홀수 for (int i = 0; i < n; ++i) { sum = sum + A[i]; } } } ``` n이 충분히 큰 경우, - 𝜪(n^2). 최대 n^2번 수행. 짝수일 때. - 𝜴(n). 최소 n번 수행. 홀수일 때. - 𝜭 없음. 빅오(𝜪)와 오메가(𝜴)가 서로 다름. ## 요약 --- - 점근적 표기 분석 => 알고리즘 평가 방법 - 점근적 표기 종류 => 빅오(𝜪: 최대 ~까지), 오메가(𝜴: 최소 ~까지), 세타(𝜭: 𝜪 = 𝜴)