[컴퓨터과학개론] 알고리즘 (2)

분석

정확성 분석: 유효한 입력이 주어졌을 때 유한한 시간 내에 정확한 결과가 나오는지

다양한 케이스를 처리할 수 있는지 확인하면서 수정해나가기

 

효율성 분석: 컴퓨터 자원(메모리)의 양과 수행 시간을 통해 평가 => 적은 메모리와 더 빠른 수행 시간

- 공간 복잡도: 총 메모리 양 = 정적인 공간과 동적인 공간의 합

- 시간 복잡도: 알고리즘 실행 시간. 최선의 수행시간 (가장 빠른 시간) / 일반적인 상황에서의 평균 수행시간 / 최악의 수행시간

 

점근 성능

입력 크기 n이 커지면서 결정되는 알고리즘 성능

입력 크키가 커질 수록 식의 최고차항을 고려해 수행 시간을 표현함

Big-oh (점근적 상한) : 입력 크기 n이 커지면 최악의 수행시간은 g(n)에 비례함 (O(g(n))

Big-omega (점근적 하한) : 좋은 상태의 입력이더라도 하한의 성능보다 더 좋을 순 없는 최선의 수행시간

Big-theta (점근적 상하한) : g(n)이 점근적 상한과 하한을 동시에 가져 정밀하게 성능을 표기 가능

 

일반적으로 O-표기법을 사용.

O(1) < O(log n) < O(n) < O(n log n ) < O(n^2) < O(n^3) < O(2^n)