반복 숙달을 통해서 알아야한다.
시간 복잡도
알고리즘의 성능을 나타내는 척도이다.
<aside> 💡 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
</aside>
값이 크게 증가하는 정도
복잡도가 낮을 수록 시간이 적게 걸린다. 결과가 금방 나온다!!!
빅오 표기법
가장 빠르게 증가하는 항만을 고려하는 표기법이다.
함수의 상한을 나타낸다.
ex)
3N^3
+ 5N^2 + 1000000 이라고 했을때 N^3
차수가 가장 큰 항에서 계수를 제외하여 표기한다. (N^3)
로그는 수학적인 관점에서 값의 크기를 빠르게 줄여준다.
상수에 가까울 정도로 빠른다.
선형시간의 예 - 배열의 요소를 하나하나 탐색해서 요소를 찾을때
이차 시간 - 동적 계획법
알고리즘 설계 TIP
일반적인 CPU 기반의 개인 컴퓨터나 채점 목적의 컴퓨터를 고려
JS 기준으로 1억 번의 연산을 처리하기 위해 1~5초 가량의 시간이 소요된다.
O(N^3) 의 설계한 경우 N이 5000이면??
5000 *5000 *5000 = 125억
1억 번에 1초~5초면
125억
이면 25초가 걸리므로 시간 제한 탈락