[알고리즘] 시간 복잡도

Big-O notation

프로그램의 성능을 알기 위해선 입력 크기, 하드웨어 성능, 운영체제 성능 .... 등 고려해야할 것이 많다. 

따라서 프로그램의 성능을 정확하게 파악하는 것은 불가능하다. 

 

그래서 대략적인 성능을 비교하기 위한 상대적인 표기법(Big-O notation)을 사용한다. 

O(1)에서 O(log n) .... O(n!)로 갈수록 점점 시간이 오래 걸린다. 

 

O(log n)과 O(n)이 눈으로 봤을 때는 크게 차이가 없는 것 같지만 n이 1024일 경우 O(n)은 1024번 반복하지만

O(log n)은 10번만 반복하게된다. 

 

O(3n - 30)이나 O(3 log n)같은 시간 복잡도는 본적이 없을 것이다. 

그 이유는 Big-O notation이 점근적 표기법을 따르기 때문이다.

 

점근적 표기법은 함수의 증감 추세를 비교하는 방법이다. 

프로그램을 쉽게 유지할 수 있도록 불필요한 부분을 버리고 가장 중요한 부분만 추려내서 함수를 간소화하는 것이다. 

6n^2 + 100n + 300 이라고 가정했을때 n의 값이 어느정도 계속 커진다고 했을 때, 6n^2은 100n + 300 보다 

커집니다. 

중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어져서 알고리즘 실행 시간에서 

중요한 부분인 성장률에 집중할 수 있다. 

 

Big-O natation 의 4가지 법칙

계수 법칙

상수 k가 0보다 클 때 f(n) = O(g(n)) 이면 kf(n) = O(g(n)) 이다. 

즉, n이 무한에 가까울 수록 k의 크기는 의미가 없다. 

합의 법칙

f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) + g(n) = O(h(n)) + O(p(n)) 이다. 

즉, Big-O 끼리는 더해질 수 있다. 

곱의 법칙

f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) * g(n) = O(h(n)) * O(p(n)) 이다. 

즉, Big-O 끼리는 곱해질 수 있다. 

다항 법칙 

f(n)이 k차 다항식이면 f(n)은 O(n^k)이다.