알고리즘의 기본, 시간 복잡도

 

시간 복잡도

주어진 문제를 해결하기 위한 연산 횟수를 의미한다.

3가지 유형 빅-오메가(최선), 빅-세타(보통), 빅-오(최악) 으로 정의 가능하며, 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.

 

시간 복잡도를 기준으로 알고리즘 선택하기

시간 제한이 2초라면, 4,000만 번 이하의 연산 횟수로 문제를 해결해야 한다. (파이썬의 경우, 1초에 2,000만 번 연산하는 것으로 생각)

 

시간 복잡도 도출 기준

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

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

 

예를 들어, 연산 횟수가 N, 3N인 코드가 각각 있다면, 각 코드의 시간 복잡도는 O(n)으로 같다.

연산 횟수가 N^2인 이중 for문을 포함한 코드가 있다면, 해당 코드 내 일반 for문이 10개 더 있더라도 시간 복잡도는 변화 없다.