시간 복잡도 표기 예

1. 시간 복잡도의 표기 例)

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

  ㅇ O(c) 또는 O(1)  :  상수 시간 알고리즘 (constant time algorithm)
     - 입력 크기(개수)에 관계없이, 항상 일정한 수행 속도(계산 횟수)
     - 가장 효율적임을 뜻함
     - 例) 배열에 있는 항목을 인덱스를 사용하여 접근할 때, 집합 내 요소로의 접근 등

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

  ㅇ O(n)  :  선형 시간(1차 시간) 알고리즘 (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(∞)