[자료구조] 알고리즘의 성능분석

알고리즘 성능 분석 기준

• 기준에는 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등 있음
  - 정확성: 올바른 자료 입력 시 유한한 시간 내에 올바른 결과 출력 여부
  • 명확성: 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는가
  • 수행량: 일반적인 연산 제외, 알고리즘 특성 나타내는 중요 연산 모두 분석
  • 메모리 사용량
  • 최적성: 가장 중요

공간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양
• 공간 복잡도 = 고정 공간 + 가변 공간

시간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간
• 시간 복잡도 = 컴파일 시간 + 실행 시간
  - 컴파일 시간: 프로그램마다 거의 고정적인 시간 소요
  • 실행 시간: 컴퓨터의 성능에 따라 달라질 수 있으므로 실제 실행시간 보다는 명령문의 실행 빈도수에 따라 계산
• 실행 빈도수의 계산
  - 지정문, 조건문, 반복문 내의 제어문과 반환문은 실행시간 차이가 거의 없으므로 하나의 단위시간을 갖는 기본 명령문으로 취급
  
• 시간 복잡도 예) 피보나치 수열 알고리즘 빈도수 구하기
  

알고리즘 성능 분석 표기법

빅-오 표기법

• O(f(n))과 같이 표기, “Big Oh of f (n)”으로 읽음
• 수학적 정의
− 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥n0에 대하여 |f(n)| ≤ c |g(n)|을 만족하는 상수 c와 n0이 존재하면, f(n) =
O(g(n))이다.
• 함수의 상한을 나타내기 위한 표기법
− 최악의 경우에도 g(n)의 수행 시간 안에는 알고리즘 수행 완료 보장
• 먼저 실행 빈도수를 구하여 실행 시간 함수를 찾고, 이 함수값에 가장 큰 영향을 주는 n에 대한 항을 한
개 선택하여 계수는 생략하고 O의 오른쪽 괄호 안에 표시
• [알고리즘 1-1]의 피보나치 수열에서 실행 시간 함수는 4n+2이고, 가장 영향이 큰 항은 4n인데 여기에
서 계수 4를 생략하여 O(n)으로 표기

• 각 실행 시간 함수에서 n값의 변화에 따른 실행 빈도수 비교
  

• 시간 복잡도에 따른 알고리즘 수행 시간 비교