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

(2023-06-13)

알고리즘 분석, 복잡도 , 계산 복잡성, 계산 효율성, 알고리즘 수행 시간, Space Complexity, 공간 복잡도


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

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

  ㅇ 소요 메모리 : 공간 복잡도 (Space Complexity)
     - 계산에 소요되는 컴퓨터 메모리


2. 알고리즘 효율성의 척도 : 계산 복잡도 (Computational Complexity, Complexity Metric)

  ㅇ 주로, 시간 복잡도 위주로 따짐
  ㅇ 다만, 최근의 빅데이터 처리에는 공간 복잡도도 점차 중요해 짐


3. 알고리즘 효율성의 분석 : 수행 시간 및 소요 메모리 분석효율성 분석
     - 알고리즘을 실행하는 데 필요한 시간,공간측정하는 것

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

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

  ㅇ 분석 방법  :  점근적 분석법
     - 입력 크기가 충분히 큰 경우에 대해, 점근적으로 분석하는 방법

     * 알고리즘 실행 시간을 정확히 측정하기 보다는, 
        . 입력 크기가 증가함에 따라, 소요 시간이 (점근적으로) 어떻게 변하는 지에 관심이 있음


4. 알고리즘 효율성의 표현

  ㅇ 표현 방식  :  다항식 함수 형태
     - 주로, `소요 공간` 보다는 `수행 시간`에 대해, 
        . 입력 크기 n에 대해, 소요되는 기본 연산 횟수가, 
        . 어떤 다항식 함수 형태(상수 시간, 선형 시간, 로그 시간 등)에 비례적인가를 나타냄
        . ☞ 시간 복잡도 표기 예  참조
     - 이는, 기계적인 속도프로그래밍 스타일과는 무관함

  ㅇ 표기 법  :  점근적 표기법 (최악, 평균, 최선)                    ☞ 시간 복잡도 참조
     - (최악의 경우, worst-case) => big-O (빅 오 표기법) : O()
        . `최악, 이정도는 보장`  (점근적 상한선)
     - (최선의 경우, best-case) => big-Omega (빅 오메가 표기법) : Ω() 
        . `최고 수준`  (점근적 하한선)
     - (평균의 경우, average-case) => big-Theta (빅 세타 표기법) : Θ()
        . `대략`  (점근적 상하한선)

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


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"