시간 복잡도 표기 예 (상수 시간, 선형 시간, 로그 시간, 평방 시간, 다항 시간, 다항식 시간, 지수 시간)

시간 복잡도의 표기

시간 복잡도는, 입력 크기의 함수적 관계식으로 표현되며,
이때 함수의 증가율을 특징지울 수 있는, 여러 부류들이 다음과 같음

• O(c) 또는 O(1) 상수 시간 알고리즘 (constant time algorithm)

  • 입력 크기(개수)에 관계없이 수행 속도(계산 횟수) 일정
  • 가장 효율적임을 뜻함
  • 예) 배열에 있는 항목을 인덱스를 사용하여 접근할 때, 집합 내 요소로의 접근 등

• O(log n) : 로그 시간 알고리즘 (logarithmic time algorithm)

  • 로그 함수 형태 알고리즘 (밑이 2인 로그함수 : log2 )
    . 통상, 데이터가 2배로 증가할 때, 연산수가 1 단계 씩 늘어나는 형태
  • 입력 개수가 증가하면서 포물선 곡선이 한쪽으로 수렴하므로,
    . 데이터가 많아질수록 우수 수행 성능
  • 예) 이진 검색

• O(n) : 선형 시간 알고리즘 (linear time algorithm)

  • 선형 함수 형태 알고리즘
    . 입력 개수에 단순 비례적으로 수행 시간이 길어짐
  • 최악의 경우에 입력 개수 만큼 연산을 수행해야 함
  • 예) 중첩되지 않은 통상의 반복문, 선형 검색, 자연수의 거듭제곱 등

• O(n log n) n 로그 시간 알고리즘 (nlogn time algorithm)

  • 예) 반복문 증가 스텝이 2의 배수로 하여 2,4,8,16,32,64 처럼 증가하는 경우 등

• O(n2) 평방 시간(2차 시간) 알고리즘 (quadratic time algorithm)

  • 문제 해결 단계의 수가 입력값 n의 제곱으로 증가
    . n이 적을 경우에 만 사용해야 하는 느리고 비효율적인 알고리즘
  • 예) 2번 중첩된 반복문(for 문), 버블정렬,삽입정렬,선택정렬 등

• O(n3) : 3차 시간 알고리즘

  • 예) 3번 중첩된 반복문(for 문) 등

• O(nk) 다항식 시간 알고리즘 (polynomial time algorithm)

  • 입력 크기에 대한 다항식으로 나타나는 알고리즘
    . 다항식 : 입력 n과, nk(n의 상수 거듭제곱)들의 선형 결합으로 이루어진 식
    . 즉, O(n),O(n2),O(n3), ... O(nk) 모두를 가리킴
  • 주로, 중첩된 반복문의 수행 횟수를, 입력 크기의 다항식으로 표현할 수 있는 알고리즘들
  • 한편,
    . 다항 시간 내 풀 수 있으면, 다루기 쉬운(tractable), P 문제 라고 하고,
    . 다항 시간 내 풀 수 없으면, 다루기 힘든(intractable), NP 문제 라고 함

• O(2n) 또는 O(rn) 지수 시간 알고리즘 (exponential time algorithm)

  • n이 하나 증가할 때 마다, 걸리는 시간이 그전보다 2배 또는 r배로 걸리는 매우 나쁜 사례

• O(n!) 계승 시간 (factorial time algorithm)

  • 지수 시간 보다 더 많이 걸림 (더 빠르게 증가함)
  • 따라서, 초 지수 시간(super-exponential)이라고도 함

• O(∞) 종료되지 않는 무한 루프

  ※ [참고] 시간복잡도 연산 크기 순서 例)
  - O(1) < O(log n) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(∞)
  .
  .
  .
  .
  .
  

참고
http://www.ktword.co.kr/test/view/view.php?m_temp1=6146