점근 표기법

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)의 기본적인 해법