[C언어/자료구조] 시간복잡도와 점근적 분석의 개념

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

시간복잡도 (time complexity)

단순 실행 시간을 분석하지는 않는다. 실행 시간은 실행환경에 따라 달라지기 때문이다. (하드웨어, 운영체제, 언어, 컴파일러 등)

실행 시간을 측정하는 대신에 연산의 실행 횟수를 카운트한다.

입력 데이터의 크기가 커지면 연산의 실행횟수도 커지므로 연산의 실행횟수를 입력 데이터의 크기에 관한 함수로 표현한다.

또한 데이터의 크기가 같더라도 실제 데이터에 따라 연산의 실행횟수가 달라질 수 있다.

따라서 평균 시간복잡도를 분석하거나 최악의 경우 시간복잡도를 분석한다.

평균 시간복잡도(average-case analysis)는 알고리즘이 복잡해질수록 구하기가 굉장히 어렵기 때문에, 비교적 구하기 쉬운 최악의 경우 시간복잡도(worst-case analysis)를 주로 사용한다.

 

⇒ 시간복잡도는 어떤 알고리즘에 대해 최악의 경우, 혹은 평균 연산 실행횟수를 입력 데이터의 크기에 관한 함수(n^2, 2n+3 등)로 표현한 것이다.

 

점근적(Asymptotic) 분석 

연산의 실행횟수를 표현한 함수에서 상수항이나 계수 등을 무시하고, 최고차항의 차수 정도만 간단하게 표기하는 방법(=점근적 표기법)이다.

데이터의 개수 n→무한대일 때, 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법이라고도 말한다.

표기법은 O- 표기(Order of n^2 / Big-Oh of n^2) 등을 사용한다.

 

점근적 분석법은 유일한 분석법이거나 가장 좋은 분석법은 아니다.

다만 상대적으로 간단하며, 알고리즘의 실행환경에 비의존적이기 때문에 가장 광범위하게 사용된다.