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

(2020-06-19)

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

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

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

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

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

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

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


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

 
        요약목록     참고문헌