[자료구조 및 알고리즘] (3) Asymptotic analysis (점근적 분석)

한국어로 점근적 분석이라고 하면 이게 뭔가 싶은데... Asymptotic analysis는 어떤 알고리즘에 매우매우 큰 사이즈 n의 input을 넣었을 때, output을 만들기 위한 과정이 얼마나 복잡해지는가??

를 알아보는 것이다. Big O notation이라고도 함. 1.

Algorithm analysis를 위한 guiding principles 1: Worst case analysis: 가장 시간/리소스가 많이 드는 경우라고 가정한다. 예를 들어 sorting의 경우, 보통 input이 거꾸로 sort되어 있으면 다시 sort하는 데 제일 오래 걸린다.

항상 이런 경우라고 가정하는 것이다. 같은 n 길이의 인풋이라도 적당히 정렬되어 있거나 하는 경우는 생각하지 않는다.

이런 점에서 average-case analysis, benchmark 등과는 다르다. 이렇게 모델링을 하려면 input에 대한 어느 정도 지식이 있어야 한다.

예를 들어 대충 어느 정도 정렬되어 있다거나,...