Computational Complexity   계산 복잡도

(2019-01-08)

계산 복잡성, 계산 효율성, 알고리즘 효율성, Time Complexity, 시간 복잡도, 빅 오 표기법

1. 알고리즘의 효율성/성능

  ㅇ 효율성 구분
     - 계산 시간   : 시간 복잡도 (Time Complexity)
        . 소요되는 기본 연산 수
     - 소요 메모리 : 공간 복잡도 (Space Complexity)
        . 소요되는 컴퓨터 메모리

  ㅇ 효율성 척도 : 계산 복잡도 (Computational Complexity,Complexity Metric)
     - 주로, 시간 복잡도 만을 대상으로 함


2. 시간 복잡도

  ㅇ 소요되는 기본 연산 수에 따름
     - 주로, 알고리즘이 사용한 기본 연산의 수에 따름
        . 주요 기본 연산 : 정수의 비교,덧셈,곱셈,나눗셈 등

  ㅇ 시간 복잡도 표현
     - 기본 연산 수가 입력 크기와 어떤 함수 관계가 있는가를 분석하고, 이를 함수식 처럼 표현

  ㅇ 시간 복잡도 표기 : big-O, big-Omega, big-Theta
     - 전체 값 계산에 가장 큰 영향을 주는 항 만 고려한, (최악의 시나리오)
     - 근사적인 표기법 (빅오 표기법)
        . 例) n2 + n + 1 => O(n2)


3. 시간 복잡도 표기 例)

  ㅇ O(c) 또는 O(1)  :  상수 시간 알고리즘 (constant time algorithm)
     - 상수알고리즘
     - 입력 크기(개수)에 관계없이 수행 속도(계산 횟수) 일정
     - 가장 효율적임을 뜻함

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

  ㅇ O(n)  :  선형 시간(1차 시간) 알고리즘 (linear time algorithm)
     - 선형 함수 형태 알고리즘
     - 입력 개수에 비례하며 수행 시간 길어짐
     - 例) 선형 검색

  ㅇ O(nlogn)  :  n 로그 시간 알고리즘 (nlogn time algorithm)

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

  ㅇ O(n2) :  평방 시간(2차 시간) 알고리즘 (quadratic time algorithm)
     - n이 적을 경우에 만 사용
     - 느리고 비효율적인 알고리즘


[알고리즘] 1. 알고리즘 2. 알고리즘 설계 3. 계산 복잡도 4. 하노이 탑 5. 순서도 6. 재귀 호출
[알고리즘 종류]

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