[자료구조/알고리즘] 시간복잡도와 빅오 표기법

시간복잡도(Time Complexity)

- 프로그램을 실행시켜 완료하는데 걸리는 시간

- 어떤 프로그램의 실행시간을 추정하기 위해서는 모든 기본 명령문의 실행 빈도수(frequency count)를 알아야한다 여기서 기본 명령문은 지정문,조건문,반복문 속의 제어문 그리고 stop, return등을 포함한다

- 추정을 목적으로 하기 때문에 프로그램 문맥상 하나의 연산 단위를 하나의 단계로 계산하면 의도한 목적 달성에 충분하다

- 시간 복잡도의 계산은 정밀하지 않다 예를 들어 N+100의 제곱은 N^2+200N+10000이 되고 N^2으로 간단히 표현한다

Big O 표기법

- 빅오 표기법(Big - O Notation)

- 알고리즘의 복잡도 또는 성능을 표현하기 위해 사용된다

- 최악의 상황을 고려한 시간 복잡도를 표현한다

정의

정수(Integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f,g가 있다

만약 ,  를 만족시키는 상수 C 와 k 가 있을 때 라고 한다

O(1) : 알고리즘의 실행시간이 입력되는 데이터의 크기에 상관없이 항상 같은 경우

O(n) : 데이터 양에 따라 비례하여 처리시간이 증가하는 알고리즘

O(n^2) : 수행성능이 입력 데이터의 크기에 따라 제곱승에 비례하여 증가하는 상황을 표현

O(2^n) : 데이터가 하나 증가할 때 마다 처리량이 두배씩 증가하는 경우

O(log n) : n이 커질수록 효율(시간복잡도)가 좋아지는 성질을 가진다

Big Omega 표기법

- 최선의 상황을 고려한 시간 복잡도를 표현한다

- 정의 

정수(Integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f,g가 있다

만약 |f(x)| >= C|g(x)| , x>k를 만족시키는 상수 C>0와 k가 있을 때 , f(x) = Ωg(x) 라고 한다

Big Theta 표기법

- 정확한 상황을 고려한 시간 복잡도를 표현한다

- 정의 

만약 f(x) = O(g(x) 인 동시에 f(x) = Ωg(x) 일때 f(x) =(g(x))라고 한다