[Algorithm] chapter01-1 시간복잡도

 

시간 복잡도(time comlpexity) 

실행 시간은 실행 환경에 따라 달라진다(하드웨어 / 운영체제 / 언어 / 컴파일러 등)

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

 

점근적 분석

점근적 표기법이란, 데이터의 개수 n->무한대 일 때, 수행시간이 증가하는 growth rate 로 시간 복잡도를 표현하는 기법이다.

 

이러한 점근적 분석의 표기법에는 총 3가지가 있다.

 

1) 빅오 O- 표기법 : upper bound를 표기하는 표기법(대부분 이 방법을 사용한다.)

2) : Ω-표기법 : lower bound를 표현

3) Θ-표기법 : upper bound와 lower bound 를 동시에 표현