가라멜의 달달한 세상 탐방

1.4 알고리즘의 분석

1) 정확성 분석

- 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성해야 함

2) 효율성 분석

- 공간복잡도 : 알고리즘을 실행시켜 완료할 때까지 필요한 총 메모리의 양

- 시간복잡도 : 알고리즘을 실행시켜 완료할 때까지 필요한 총 메모리의 양 

1.5 점근성능

-n이 무한대로 커짐에 따라 결정되는 성능

- 어림값으로 표현되기 때문에 알고리즘의 정확한 수행시간은 알 수 없지만, 입력 크기가 증가함에 따라 알고리즘의 수행시간이 어떤 추세로 증가하는지를 쉽게 파악할 수 있어서 알고리즘의 우열을 따질때 용이

<표기법>

O 표기

오메가 표기

세타 표기