«   2018/01   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
Archives
Today
245
Total
1,047,584
관리 메뉴

Blue Breeze

알고리즘 복잡도 본문

IT/ETC...

알고리즘 복잡도

푸른바람 푸른_바람 2016.12.02 08:30

복잡도

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)의 기본적인 해법
0 Comments
댓글쓰기 폼