Computational Complexity   계산 복잡도

(2019-12-05)

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

1. 알고리즘효율성/성능효율성 구분
     - 계산 시간   : 시간 복잡도 (Time Complexity)
        . 소요되는 기본 연산 수
     - 소요 메모리 : 공간 복잡도 (Space Complexity)
        . 소요되는 컴퓨터 메모리효율성 척도 : 계산 복잡도 (Computational Complexity,Complexity Metric)
     - 주로, 시간 복잡도 만을 대상으로 함
        . 다만, 최근의 빅데이터 처리에는 공간 복잡도도 중요해 짐

  ※ 알고리즘 효율성은, 계산에 필요한 자원의 소요 량(量)이 적을수록 좋은 것 임


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

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

  ㅇ 시간 복잡도의 여러 명칭/의미
     - big-O (빅 오 표기법) : 점근적 상한선, O()
        . (아무리 나빠도 시간이 이보다 덜 걸림, 최악의 시나리오)
        . 주로, 빅 오 표기법을 사용함
     - big-Omega (빅 오메가 표기법) : 점근적 하한선, Ω()
        . (최소 이만한 시간이 걸림)
     - big-Theta (빅 세타 표기법) : 빅 오,빅 오메가 표기법의 절충(즉,교집합), Θ()

  ㅇ 시간 복잡도의 고려 사항 (빅 오 표기법에 준함)
     - 전체 값 계산에 가장 큰 영향을 주는 항 만 고려함 (최악의 시나리오)
        . 즉, 근사적인 것 임

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


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(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. 알고리즘 설계 3. 계산 복잡도 4. 하노이 탑 5. 순서도 6. 재귀 호출
[알고리즘 종류]
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 알고리즘 설계
            3. 계산 복잡도
            4. 하노이 탑
            5. 순서도
            6. 재귀 호출
        1.   알고리즘 종류
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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