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

(2020-06-19)

복잡도, 계산 복잡성, 계산 효율성

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

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

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

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

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

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


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

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