Time Complexity   시간 복잡도

(2020-06-19)

빅 오 표기법, 빅 세타 표기법

1. 시간 복잡도 (Time Complexity)시간 복잡도의 산정 기준  :  연산 수
     - 소요되는 기본 연산 수에 의거함
        . 주로, 알고리즘이 사용한 기본 연산의 수(명령 수,스텝 수)에 따름
        . 여기서, 주요 기본 연산으로는, 데이터의 비교,덧셈,곱셈,나눗셈 등이 있음

  ㅇ 시간 복잡도의 표현 방식  :  함수적
     - 기본 연산 수가 입력 크기(n : 입력의 개수)와 어떤 함수 관계가 있는가를 분석하고,
        . 여기서, 입력 크기의 例는,
           .. 정렬을 하려는 경우 : 정렬 대상이 되는 원소의 수 
           .. 계승 계산을 하는 경우 : 계승 계산을 하고자 하는 자연수
           .. 최단거리를 구하는 경우 : 노드의 수 및 간선의 수
     - 이를 함수식 처럼 표현 함

  ㅇ 시간 복잡도의 분석 방법  :  점근적
     - 입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따지는,
     - `점근적 분석 방법`을 씀
     
  ㅇ 시간 복잡도의 분석 종류  :  (아래 2.항 참조)
     - (최악의 경우) => big-O (빅 오 표기법) : O() => `최악, 이정도는 보장` (점근적 상한선)
     - (최선의 경우) => big-Omega (빅 오메가 표기법) : Ω() => `최고 수준` (점근적 하한선)
     - (평균의 경우) => big-Theta (빅 세타 표기법) : Θ() => `대략`

  ㅇ 시간 복잡도의 계산 방식
     - 주로, 빅 오 표기법(점근적 상한선)에 준하여,
     - 전체 값 계산에 가장 큰 영향을 주는 항 만 고려함 (즉, 최악의 시나리오)
     - 즉, 근사적인 것을 구함 


2. 시간 복잡도의 분석 종류 

  ㅇ (최악의 경우)
     - big-O (빅 오 표기법) : O() => `기껏해야` 
        . 점근적 상한선
           .. (아무리 나빠도 시간이 이보다 덜 걸림, 최악의 시나리오)
        . 주로, 빅 오 표기법을 사용함

  ㅇ (최선의 경우)
     - big-Omega (빅 오메가 표기법) : Ω()=> `적어도`
        . 점근적 하한선
           .. (최소 이만한 시간이 걸림, 최선의 시나리오)

  ㅇ (평균의 경우)
     - big-Theta (빅 세타 표기법) : Θ() => `대략`
        . 빅 오,빅 오메가 표기법의 절충 (즉,교집합)


3. 시간 복잡도의 주요 계산 例

  ㅇ 가장 큰 차수 만 고려 : 例) n2 + n + 1 => O(n2)
  ㅇ 계수는 1 로 함 : 例) 3n => O(1n) => O(n)
  ㅇ 작은 차이는 무시 : 例) O(n-1) => O(n)
  ㅇ 규모가 큰 것 만 고려 : 例) O(2n + n2) => O(2n)


4. 시간 복잡도의 주요 표기 例)

  ※ ☞ 시간복잡도 표기 예 참조
     - O(c) 또는 O(1)  :  상수 시간 알고리즘 (constant time algorithm)
     - O(log n)  :  로그 시간 알고리즘 (logarithmic time algorithm)
     - O(n)  :  선형 시간(1차 시간) 알고리즘 (linear time algorithm)
     - O(n log n)  :  n 로그 시간 알고리즘 (nlogn time algorithm)
     - O(n2)  :  평방 시간(2차 시간) 알고리즘 (quadratic time algorithm)
     - O(n3)  :  3차 시간 알고리즘
     - 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. 시간 복잡도 3. 시간 복잡도 표기 예
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   전기전자공학
  5.   방송/멀티미디어/정보이론
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
          1.   1. 알고리즘 효율성
              2. 시간 복잡도
              3. 시간 복잡도 표기 예
        2.   알고리즘 종류
        3.   알고리즘 전략
        4.   (기타 알고리즘)
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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