Algorithm, 알고리즘 개념 정리

Algorithm, 알고리즘

• 사전적 정의 : 연산
• 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야하는 일련의 과정
• 문제를 해결하기 위한 여러 동작들의 단계적 집합

Algorithm 특징

• 입력 : 외부에서 제공되는 0개 이상의 자료 값
• 출력 : 입력에 따라 다른 최소 1개 이상의 결과 값
• 명확성 : 명확한 수행 과정 명령어 구성
• 유한성(종결성) : 무한히 반복되지 않도록 정해진 로직 안에서 정해진 시간 내에 출력
• 유효성 : 반드시 모든 명령들이 실행 가능해야 함
• 일반성 : 요구되는 모든 입력에도 적용 가능해야 함
• 효율성 : 시간 복잡도(계산 시간), 공간 복잡도(소요 메모리)의 최소 소요 량

Algorithm 표현

• 일상 언어, 의사 코드, 흐름도(순서도), 프로그래밍 언어 등을 사용하여 문제를 해결하는 과정을 기술하는 수단,

• 의사 코드 (Pseudocode)

  • 자연 언어와 프로그래밍 언어의 중간 단계 언어
  • 형식적이고 명확한 문장, 제어 구조는 갖추고 있으나 구현되지 않음

Algorithm 효율성

• Algorithm 효율성은 시간과 공간 측면에서 계산에 필요한 자원의 소요 량이 적을수록 좋은 것

- 효율성 구분

• 시간 복잡도, Time complexity : 알고리즘 수행 시간 동안 사용된 기본 연산의 수
• 공간 복잡도, Space complexity : 연산에 소요되는 메모리

Big data 처리에는 공간 복잡도도 점차 중요해지고 있지만 주로 알고리즘 효율성 척도의 기준은 시간 복잡도이다.

- 효율성 분석

• 입력 값의 크기에 따라 시간 복잡도와 공간 복잡도의 증가 값을 분석

  • 입력 값의 크기
    • 배열의 크기
    • 다항식 차수
    • 행렬의 항목 수
    • 이진 입력 비트 수
    • 그래프의 정점 및 가지 수

• 수행 시간 표현

  • 입력 값 크기 n에 따른 함수 f(n)으로 표현 가능

Algorithm 수행 구조

• 조건문 등과 같은 별도 지시의 명령어 유무에 따라 나뉜다.
  • 순차 구조
  • 선택 구조
  • 반복 구조

Algorithm 분류

• 주제 별 분류
  • 탐색 알고리즘
    • 선형 탐색, 이진 탐색 등
  • 정렬 알고리즘
    • 버블, 선택, 삽입정렬 등
  • 그래프 알고리즘
• 설계 기법/전략/패러다임에 의한 분류
  • 분할 정복
  • 탐욕
  • 동적 프로그래밍

Reference

http://www.ktword.co.kr/abbr_view.php?nav=2&id=507