알고리즘에서 시간 복잡도는주어진 문제를 해결하기 위한 연산 횟수
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주
🟡 시간 복잡도 유형
- 빅-오메가: 최선일 때(best case)의 연산 횟수를 나타낸 표기법
- 빅-세타: 보통일 때(average case)의 연산 횟수를 나타낸 표기법
- 빅-오: 최악일 때(worst case)의 연산 횟수를 나타낸 표기법
* 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음
🟡 시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외한다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
🟡 시간 복잡도 그래프
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 브루트 포스(brute force) 알고리즘 (0) | 2023.01.16 |
|---|---|
| [알고리즘] 재귀(Recursion), 재귀 호출(Recursive call) (0) | 2023.01.02 |
| [알고리즘] 투 포인터, 슬라이딩 윈도우(two pointers, sliding window) (0) | 2022.12.14 |
| [알고리즘] 정렬 - 버블 정렬(bubble sort) (0) | 2022.11.28 |
| [알고리즘] 구간 합 알고리즘(Prefix Sum) (0) | 2022.11.10 |
댓글