시간 복잡도

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다.

시간 복잡도 유형

빅-오메가: 최선일 때 연산 횟수를 나타낸 표기법

빅-세타: 보통일 때의 연산 횟수를 나타낸 표기법

빅-오: 최악일 때의 연산 횟수를 나타낸 표기법

코딩 테스트에서는 빅 - 오 표기법 O(n)을 기준으로 수행 시간을 계산하는 것이 좋다.

 

연산 횟수 계산 방법

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

연산 횟수는 1초에 1억 번 연산하는 것을 기준으로 생각한다.

 

알고리즘 적합성 평가

1,000,000 개의 수를 정렬하는 문제일 경우에

버블 정렬 O(n^2)은 1,000,000 * 1,000,000 = 약 10억 번 연산

병합 정렬 1,000,000 * log(1,000,000) = 약 2,000만번 연산

데이터의 크기(N)을 단서로 사용하여 알고리즘을 추측해 볼 수 있다.

 

시간 복잡도 도출 기준

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

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