20.08.03 Time Complex 정리

여기서 시간복잡도의 종류에 대해 간단하게 복습해보자면 (위에서 아래로 갈수록 worst한 복잡도이다)

 

시간복잡도

• constant : 특정 상수로 '한번' 실행했을 때 결과가 나오는 경우 O(1)
• logarithmic : log n의 시간복잡도를 가지는 경우이다. 초반에는 다소 급격하게 증가하지만 이후로는 거의 복잡도가 증가하지 않는 형태를 보이고 있다. O(log n)
• linear : 선형 그래프를 그린다. 흔히 보는 y =x의 그래프의 형태로 시간복잡도가 증가한다. 대표적인 예로는 linked list의 탐색의 경우이다. O(n)
• quadratic : n^2의 형태로 복잡도가 증가하는 형태이다. 흔히 보는 y=x^2의 2차 방정식의 그래프 형태를 띄고 있다. 여기서부터는 알고리즘을 짤 때 피해야하는 시간복잡도이다. n이 3만 되어도 9로 증가하기 때문에 컴퓨터가 멈출수도 있기 때문이다. O(n^2)
• exponential : 단순히 제곱으로만 증가하는 것이 아니라 특정 상수C의 n승 만큼 증가하게 된다. C가 3이고 n이 3만 되어도 3^3으로 27번의 연산을 해야하므로 반드시 피해야하는 시간복잡도이다. O(C^n)

 

데이터 타입별 시간 복잡도 정리해 둔 사이트

: Big-O 유형 정리해둔 사이트