점근 표기법: Difference between revisions
From CS Wiki
(새 문서: ;Big-O Notation ;알고리즘 성능 측정 기준 * O(1) : 입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘 * O(log N) : 입력 자료의 크기...) |
No edit summary |
||
| Line 1: | Line 1: | ||
[[분류:알고리즘]] | |||
;Big-O Notation | ;Big-O Notation | ||
;알고리즘 성능 측정 기준 | ;알고리즘 성능 측정 기준 | ||
Latest revision as of 09:26, 14 June 2019
- 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)의 기본적인 해법
