시간 복잡도 표기법

수행시간은 1억번의 연산을 1초의 시간으로 간주한다. 

 

* 제한시간이 2초면 -> 2억번 이하의 연산 횟수로 문제를 해결해야함

연산횟수 = 알고리즘 시간 복잡도 * 데이터의 크기

 

버블정렬 : O(n^2)

병합정렬 : O(nlogn)

=> N이 1,000,000 이라고할때 대입해보면 2억번보다 큰 버블정렬은 부적합 알고리즘이다.

 

* 시간 복잡도 도출 기준 

1. 상수는 시간 복잡도 계산에서 제외한다.

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.