IT용어위키



점근 표기법

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

  출처: 공대위키(공대위키에서 최신 문서 보기)
  * 본 페이지는 공대위키에서 미러링된 페이지입니다. 일부 오류나 표현의 누락이 있을 수 있습니다. 원본 문서는 공대위키에서 확인하세요!