it/etc

알고리즘 복잡도

C/H 2016. 12. 2. 08:30

복잡도

O(1)
입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘
O(log N)
입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다.
O(N)
입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다.
O(N log N)
입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다.
O(N2)
입력 자료의 크기가 N일경우 N^2 번만큼의 수행시간을 가진다.
O(N3)
입력 자료의 크기가 N일경우 N^3 번만큼의 수행시간을 가진다.
O(2n),
입력 자료의 크기가 N일경우 2^N 번만큼의 수행시간을 가진다.
O(n!)
입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다. 일반적인 알고리즘 문제의 기본 해법은 대부분 이 수행시간을 가진다.ex)외판원 문제(TSP)의 기본적인 해법


반응형