알고리즘 선택의 기준이 되는 시간 복잡도

문제마다 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것이다. 입력의 크기를 보고 완전탐색 또는 이진 탐색을 구분하듯 시간 복잡도를 고려해서 문제를 접근해야 한다.

시간 복잡도 표기법 알아보기

일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다.

예) 시간 제한 2초이면 worst-case(빅오)가 2억번의 연산보다 작은 연산인지 생각해야 한다.
➡️ 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출한다.

시간 복잡도 유형

빅-오메가Ω(n) : best-case의 연산 횟수를 나타낸 표기법
빅-세타Θ(n) : average-case의 연산 횟수를 나타낸 표기법
빅-오O(n) : worst-case의 연산 횟수를 나타낸 표기법