복잡도를 배우는 이유

• 구현하려는 알고리즘을 실제로 프로그래밍해 보지 않아도 시간을 미리 대략적으로 파악

복잡도와 빅오 표기법

빅오, 빅오메가, 빅세타

빅오 - 상한

• 제일 느릴때를 측정

빅오메가 - 하안

• 제일 빠를때를 측정

빅세타 - 평균

변수는 넣어주어야 한다.

input A = N

input B = M

O(N+M)

→ 인풋 크기가 다르면 위와 같이 계산해주어야함

→ 인풋 값의 크기를 잘보기

루트랑 로그 비교

Python Algorithm class (log n 과 √n 비교)

로그가 나오면 이진 탐색이라 보면 된다.