Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 행렬식
- 한국데이터산업진흥원
- 메가존아이티평생교육원
- 중간고사
- 학점은행제
- 선형대수학
- lte라우터
- 머신러닝
- 행렬식 파이썬
- 라이프니츠 공식
- 화웨이라우터
- 원격평생교육진흥원
- 알고리즘
- 정규방정식
- 가우스조르당소거법
- 컴공수학
- 학사
- LU분해 알고리즘 구현
- 정보처리기사 후기
- 선형회귀모델
- LU분해 파이썬
- 행렬식의 정의
- 가우스조던소거법
- 한국기술교육대학교
- 김영평생교육원
- 여인수 전개
- 정보처리기사 기출
- LU분해
- determinant
- 컴퓨터공학
Archives
- Today
- Total
gyeo-ri.com
[알고리즘] 복잡도와 점근적 표기법(빅오 표기법, 빅오메가 표기법, 세타 표기법) 본문
*한국기술대학교 원격평생교육원에서 수강중인 학점은행제 컴퓨터공학 학사 과정의 알고리즘 요약 자료(시험 대비)입니다.
<점근적 표기법>
복잡도의 점근적 표기
- 점근적 분석 : 입력의 크기가 충분히 큰 경우에 대한 분석
- 입력 크기가 작은 문제 : 알고리즘의 효율성이 중요하지 않음(비효율적인 알고리즘도 큰 문제가 없음)
- 입력 크기가 충분히 큰 문제 : 알고리즘의 효율성이 중요(비효율적인 알고리즘이 치명적)
- 복잡도는 입력 크기에 대한 함수로 표기하며, 이 함수는 주로 여러 개의 항을 가지는 다항식
- 다항식을 단순한 함수로 표현하기 위해 점근적 표기법 도입
- n의 크기가 커짐에 따라 최고차항을 제외한 나머지 항의 비중이 줄어들기 때문에, 일반적으로 최고차항만을 표기
O(Big-Oh) 표기법
- 점근적 상한선, 최악의 경우의 알고리즘 수행 시간을 나타냄
- 최악의 경우에도 성능을 보장하기 때문에 가장 많이 사용하는 알고리즘 성능 표기 방식
- 실제 시간 복잡도(f(n))가 특정 n값 이상에서 항상 추정 시간 복잡도(c*g(n))보다 작음을 증명하여, 최고차항의 계수와, 최고차항 이외의 모든 항을 제거하고 단순한 형태인 O(n)과 같이 표기할 수 있는 근거를 만듦
- 적어도 O(g(n))보다 나빠지지 않음
Ω(Big-Omega) 표기법
- 점근적 하한선, 최선의 경우 알고리즘 수행 시간을 나타냄(위험성이 큰 가정이므로 거의 사용되지 않음)
- 실제 시간 복잡도(f(n))가 특정 n값 이상에서 항상 추정 시간 복잡도(c*g(n))보다 큼을 증명하여, 최고차항의 계수와, 최고차항 이외의 모든 항을 제거하고 단순한 형태인 Ω(n)과 같이 표기할 수 있는 근거를 만듦
- 적어도 Ω(g(n))보다 좋아지지 않음
Θ(Theta) 표기법
- 점근적 상한선과 점근적 하한선의 교집합
- n0보다 큰 모든 n에 대해 f(n)이 상한과 하한을 동시에 만족함을 의미
'Study Note > 알고리즘' 카테고리의 다른 글
[알고리즘] 정렬 알고리즘 (0) | 2020.09.28 |
---|---|
[알고리즘] 점화식과 수열 알고리즘 (0) | 2020.09.27 |
Comments