TIL 50일차_시간복잡도(Time Complexity)

시간복잡도 란?

시간복잡도를 한문장으로 정리하면 "입력값이 커짐에 다라 증가하는 시간의 비율" 이라고 할 수 있다.

이 시간 복잡도를 표기하는 방법은 여러가지가 있지만, Big-O 표기법 (빅오표기법) 이 가장 흔하게 사용된다.
Big-O표기법은 최악의 경우 입력값이 증가함에 따라 시간복잡도가 얼마나 증가하는지 표기하는 방법이다.

Big-O 표기법의 종류

아래는 빠른 시간복잡도 순으로 나열한 것이다.
O(1) - O(logn) - O(n) - O(nlogn) - O(n^2) - O(2^n) - O(n!)

빅오표기법을 표기할 때는,
계수나 정수값들은 생략한다.
예를 들어, 입력값이 1 증가할때마다 코드의 실행시간이 2초씩 증가한다고 하면,
'이 알고리즘은 O(2n) 이구나!' 라고 생각할 수 있지만,
실제 표기법은 O(n)이다.

그 이유는,
빅오표기법은 항상 최악의 경우를 가정하기 때문이다.
입력값이 무한에 가깝게 커지면 커질수록, 계수(n앞에 있는 수)의 의미(영향력)도 점점 퇴색되기 때문에,
이를 생략하고 O(n)으로 표기하는 것이다.

코딩테스트에서 시간복잡도 예상해서 문제 접근하기

코딩테스트에서는 일반적으로
입력되는 데이터의 크기를 제한해주므로 이를 토대로 어느정도의 시간복잡도까지는 괜찮을지 추측해볼 수 있다.

예를 들어 입력 데이터 n의 제한이 1,000,000이하의 수라고 했을 때,
최악의 경우 1,000,000이 데이터로 들어가게 된다.
이때는 시간복잡도가 비교적 빠른 O(n) 혹은 O(logn)가 되도록 프로그램을 작성해야 한다.
만약 O(n^2)의 시간복잡도로 프로그래밍하면 ( 예를 들어, 이중반복문)
1,000,000,000,000라는 처리하기 힘든 숫자가 나오게 된다.

반대로 데이터 크기 제한이 적을경우, 시간복잡도에 큰 신경을 쓰지 않고 문제를 풀어도 무방하다.

대략적인 데이터크기에 따른 시간복잡도는 다음과 같다.