Algorithm Efficiency, Computational Complexity   알고리즘 효율성, 계산 복잡도

(2020-01-15)

복잡도, 계산 복잡성, 계산 효율성, Time Complexity, 시간 복잡도, 빅 오 표기법, 빅 세타 표기법

1. 알고리즘효율성/성능알고리즘 효율성은, 계산에 필요한 자원의 소요 량(量)이 적을수록 좋은 것 임
     - 시간공간 측면에서 효율적인 것이 좋은 알고리즘 임

  ㅇ 효율성 구분
     - 계산 시간   : 시간 복잡도 (Time Complexity)
        . 주로, 수행 시간 관점에서, 알고리즘이 사용한 기본 연산의 수 (스텝 수,명령 수)
        . 주요 기본 연산 : 정수의 비교,덧셈,곱셈,나눗셈 등

     - 소요 메모리 : 공간 복잡도 (Space Complexity)
        . 계산에 소요되는 컴퓨터 메모리효율성 척도 : 계산 복잡도 (Computational Complexity, Complexity Metric)
     - 주로, 시간 복잡도 만을 대상으로 함
     - 다만, 최근의 빅데이터 처리에는 공간 복잡도도 점차 중요해 짐

  ㅇ 효율성 분석 : 수행 시간 및 소요 메모리 분석
     - 문제의 입력 크기가 증가함에 따라, 
        . 처리 시간(연산 수) 및 소요 메모리가 얼마나 증가하는가를 분석함

     - 입력 크기 例)
        . 배열의 크기, 다항식 차수, 행렬의 항목 수, 이진 입력 비트 수,
          그래프에서 정점 및 가지 등

     - 주로, 수행 시간을,
        . 입력 크기 n에 따른 함수 f(n)으로 표현 가능
        . 이는 기계적인 속도프로그래밍 스타일과는 무관함


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

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

  ㅇ 시간 복잡도의 분석 방법
     - 입력 크기가 충분히 클 때인 경우에 대한 `점근적 분석 방법`을 씀
     
  ㅇ 시간 복잡도의 분석 종류 (아래 3.항 참조)
     - (최악의 경우) => big-O (빅 오 표기법) : O() => `기껏해야` (점근적 상한선)
     - (최선의 경우) => big-Omega (빅 오메가 표기법) : Ω() => `적어도` (점근적 하한선)
     - (평균의 경우) => big-Theta (빅 세타 표기법) : Θ() => `대략`

  ㅇ 한편, 순환/재귀호출의 경우에, 점근적 복잡도 분석 방법 셋
     - 반복 대치, 추정증명, 마스터 정리

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


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

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

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

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


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

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


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

  ※ ☞ 시간복잡도 표기 예 참조
     - 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. 시간 복잡도 표기 예

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