[자료구조] 빅 오

빅 오 표기법

만약 시간복잡도가 T(n) = n**2 + 2n +1 인 알고리즘이 있다고 해보자 

빅 오 는 함수 T(n)에서 가장 영향력 있는 큰 부분을 찾아내는 것이다. 

T(n) = n**2 + 2n +1 의 빅 오는 n**2이다.

n	n**2	2n	T(n)	n**2의 비율
10	100	20	120	83%
100	10000	200	10200	98%
1000	1000000	2000	10002000	99.8%
10000	100000000	20000	1000020000	99.98%

빅 오 표기법의 일반화

T(n) = a*n**m + b*n**m-1 .... ->O(n**m)

대표적인 빅 오

O(l) 상수형 빅오 : 데이터 수에 상관없이 연산횟수가 고정인 유형

O(logn) 로그형 빅 오: 데이터 수의 증가율에 비해서 연삿횟수의 증가율이 훨씬 낮은 알고리즘

O(n) 선형 빅 오: 데이터수와 연산횟수가 비례

O(nlogn) 선형로그형 빅 오 : 데이터 수가 2배로 늘데, 연삿횟수는 2배를 조금 넘게 증가하는 알고리즘

O(n**2) 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘

O(n**3) 데이터 수의 3제곱 해당하는 연산횟수 

O(2**n) 지수형 빅오, 사용하는데 무리가 있음