알고리즘의 분석

• 알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 대부분 그 자원은 시간이다.
• 알고리즘을 이용할 구현 기술의 모델을 정의하는 것이 좋음. (ex RAM 모델)

RAM(random-access machine)모델

• 명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다.
• 명령어와 비용도 정확히 하는 것이 좋지만 지루함.(하려고 하지 말자)
• RAM 모델을 남용하기 보다는 실제 컴퓨터가 어떤 식으로 설계되어 있는지 참고하는 것이 좋음
• RAM 의 명령어 - 상수 시간이 걸림
  • 산술연산 ( 덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, 내림, 올림)
  • 데이터 이동 연산 (읽기, 저장하기, 복사하기)
  • 제어 연산 ( 조건 분기, 무조건 분기, 함수 호출, 리턴)
• 단, 워드 크기가 임의로 커지지 않는다는 조건 하에 ( 한번에 처리하는 양이 많은 데 상수시간이 걸리는 건 불가능하다.)
• 지수 연산 등 예외 연산도 있을 수 있다.
  • 많은 시간이 걸릴 거 같지만 2를 곱하는 경우 시프트 연산으로 상수시간에 처리 가능
• 캐시나 가상 메모리 등을 포함하지 않는다. (일부 계산 모델에서 고려)
• 알고리즘 분석시 필요한 수학적 지식
  • 조합론
  • 확률론
  • 대수기법
  • 식에서 가장 중요한 인자를 알아내는 기법

분석

• 입력 크기 : 주어진 문제에 따라 다르다.
  • 가장 자연스러운 척도는 입력 항목의 개수 (정렬, 이산 푸리에 변환 등)
  • 필요한 총 비트수 ( 두 정수를 곱하는 문제)
  • 두개의 값으로 표현하기도 함 ( 입력이 그래프인경우 ; 노드와 간선의 개수)
• 수행시간 : 기본 연산 개수 또는 실행된 단계의 횟수
• 최악의 경우 수행시간의 장점
  1. 모든 입력의 수행시간에 대한 상한이 됨 - 이 시간보다 오래 걸리지 않음을 확신할 수 있음
  2. 최악의 경우가 생각보다 빈번함 (검색에서 값이 없는 경우 등)
  3. 평균적인 경우가 최악의 경우만큼 좋지 않은 경우가 가끔 있음
• 평균 수행시간을 쓰는 게 좋을 때도 있음
• 증가 차수 : 증가 비율
  • 어떤 알고리즘이 다른 알고리즘보다 최악의 경우 수행시간이 더 낮은 증가 차수를 가질 때 더 효율적이라고 한다.

---

출처

Introduction to algorithm 3rd edition