[알고리즘] 2강. 알고리즘 소개 (2)

방송통신대학교 알고리즘 강의 정리 자료입니다.

 

1. 알고리즘 분석

정확성 분석

: 유효한 입력에 대해 유한 시간 내에 정확한 결과의 생성 여부를 확인하는 것으로 수학적 기법을 사용한 이론적인 증명 과정임.

 

효율성 분석

: 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정 및 평가하는 것으로 공간 복잡도(space complexity, 메모리의 양 = 정적 공간 + 동적 공간)과 시간 복잡도(time complexity, 수행시간: 알고리즘의 실행에서부터 완료까지 걸리는 시간)으로 평가함.

 

시간 복잡도를 측정하는 방법

- 컴퓨터에서 실행시켜 실제 수행시간을 측정하는 방법

: 실행 환경에 종속적이므로 일반성이 결여된 방법임. 컴퓨터 속도, 구현에 사용된 프로그래밍 언어, 프로그래밍 작성 방법, 컴파일러의 효율성 등에 따라 시간이 달라짐.

 

- 알고리즘 수행시간 = ∑{각 문장(연산)이 수행되는 횟수}

: 수행시간에 영향을 미치는 요인으로는 입력크기(입력되는 데이터의 크기, 문제가 해결하려는 대상이 되는 개체의 개수 / 예: 리스트 원소의 개수, 행렬의 크기, 그래프의 정점의 수 등)와 입력 데이터의 상태가 있음.

입력크기 n이 커질수록 수행시간도 증가함. 그러므로 단순히 단위 연산이 수행되는 개수의 합으로 표현하는 것은 부적절하며, 입력 크기 n의 함수 f(n)으로 표현함. [ 예시:  f(n) = 2n + 1 ]

입력 데이터의 상태에 종속적이라는 특성을 평가하기 위해서는 평균 수행시간, 최선 수행시간, 최악 수행시간 등을 사용할 수 있으며, 일반적으로 최악 수행시간을 기준으로 알고리즘의 우열을 평가함.

 

2. 점근 성능

점근성능이란?

: 입력크기 n이 무한히 커짐에 따라 결정되는 성능으로 입력 크기가 충분히 커짐에 따라 함숫값에 가장 큰 영향을 미치는 차수를 찾는 것이 점근성능을 결정하는 방법임. 수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현함.(예시: 2n^2+3n+5 → n^2, 3n+3 → n)

수행시간의 정확한 값이 아닌 어림 값이기에 수행시간의 증가 추세를 파악하는 것은 쉽고, 알고리즘 간의 우열을 따질 때 유용함.

점근성능의 표기법(Big-oh 표기법, Big-omega 표기법, Big-theta 표기법)

주요 O-표기 간 연산 시간의 크기 관계

알고리즘의 시간 복잡도 구하기

: 기본 연산의 수행 횟수의 합 f(n)을 구한 후, f(n)=O(g(n))을 만족하는 최소 차수의 함수 g(n)을 찾음. 즉, 알고리즘의 모든 문장이 아닌 루프의 반복 횟수만을 조사하여 최고 차수를 시간 복잡도로 취함. O(최고차수)

 

3. 순환 알고리즘

순환(recursion, 재귀) 알고리즘이란?

: 알고리즘의 수행과정에서 자기 자신의 알고리즘을 다시 수행하는 형태로, 시간 복잡도는 점화식으로 표현하게 됨.

점화식의 폐쇄형 구하기