시간 복잡도 표기 예

(2020-01-15)
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이 적을 경우에 만 사용
     - 느리고 비효율적인 알고리즘
     - 例) 2번 중첩된 반복문(for 문), 버블정렬,삽입정렬,선택정렬 등

  ㅇ O(n3)
     - 例) 3번 중첩된 반복문(for 문) 등

  ㅇ O(2n)  :  지수 시간

  ㅇ O(n!)  :  계승 시간 (Factorial Time Algorithm)
 
  ㅇ O(∞) :  종료되지 않는 무한 루프

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


[알고리즘 효율성] 1. 알고리즘 효율성 2. 시간 복잡도 표기 예

 
        최근수정     요약목록     참고문헌