점근 표기법: 두 판 사이의 차이
IT위키
(새 문서: ;Big-O Notation ;알고리즘 성능 측정 기준 * O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘 * O(log N) : 입력 자료의 크기...) |
편집 요약 없음 |
||
| 1번째 줄: | 1번째 줄: | ||
[[분류:알고리즘]] | |||
;Big-O Notation | ;Big-O Notation | ||
;알고리즘 성능 측정 기준 | ;알고리즘 성능 측정 기준 | ||
2019년 6월 14일 (금) 23:26 기준 최신판
- Big-O Notation
- 알고리즘 성능 측정 기준
- O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
- O(log N) : 입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.
- O(N) : 입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.
- O(N log N) : 입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.
- O(N2) : 입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다.
- O(N3) : 입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다.
- O(2n) : 입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다.
- O(n!) : 입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. ex)외판원 문제(TSP)의 기본적인 해법
