01. 어떤 알고리즘으로 풀어야 할까?

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

시간 복잡도 => 문제를 해결하기 위한 연산 횟수
(1억번 연산 -> 1초로 계산)

-시간 복잡도 정의하기
빅-오메가 : 최선일 때의 연산 횟수
빅-세타 : 보통일 때의 연산 횟수
빅-오 : 최악일 때의 연산 횟수

-코테에서는 어떤 시간 복잡도를 사용해야 할까?
빅-오를 기준으로 수행 시간을 계산해야 한다.

빅-오 표기법 기준으로 수행 시간
O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn)

• 오른쪽으로 갈 수록 효율적이라고 할 수 있다.

시간 복잡도 활용하기

-연산 횟수 계산 방법
: 알고리즘 시간 복잡도 x 데이터의 크기

-시간 복잡도 도출 기준
1. 상수는 시간 복잡도에 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.