▶ 시간 복잡도 표기 종류
- Best case
- Average case
- Worst case
-. 가장 많이 사용되는 방식은 Big-O 표기법을 사용
Big-O - 최악의 경우를 나타냄 (상한 접근)
O(n): 최악의 경우 n번까지 수행되면 프로그램을 끝낼 수 있다.
Big-Omega - 최적의 경우를 나타냄 (하한 접근)
O(n): 최소 번은 수행되어야 프로그램을 끝낼 수 있다.
Theta - 평균 (Big-O 와 Big-Omega값의 평균값)
▶ 시간 복잡도 다른 표현 방법
Every-case anlaysis
- 입력크기(input size)에만 종속
- 입력값과는 무관하게 결과값은 항상 일정
): Worst-case analysis
- 입력크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최대인 경우 선택
): Average-case analysis
- 입력크기와 입력값 모두에 종속
- 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
- 각 입력에 대해서 확률 할당 가능
): Best-case analysis
- 입력크기와 입력값 모두에 종속
- 단위연산이 수행되는 횟수가 최소인 경우 선택
Computer algorithm을 이해하기 위해선, 시간과 공간의 복잡도를 이해 할 수 있어야 한다.
'Computer Science > 대학원 기록' 카테고리의 다른 글
| 신경 정보 처리 - midterm examination / 5월 9일(화) (0) | 2023.05.17 |
|---|---|
| [인공지능개론] Fisher Discriminant Analysis - FDA (0) | 2023.04.26 |
| [컴퓨터 알고리즘] in place / not in place 정렬 알고리즘 (0) | 2023.04.13 |
| [Computer Vision] Histogram Equalization (0) | 2023.03.25 |
| [메모] zoom recodings 다운로드 (0) | 2023.03.22 |