⇦

개강까지 D-39!

🌱 알고리즘
✅ 복잡도

시간복잡도: 특정한 크기의 입력에 대하여 얼마나 오래 걸리는가 = 필요한 연한의 횟수
공간복잡도: 특정한 크기의 입력에 대하여 얼마나 많은 메모리 차지하는가 = 필요한 메모리의 양

–> 메모리를 더 많이 사용해서 시간을 줄이는 방법? Memoization

🟢 시간 복잡도
Big-O: 가장 빠르게 증가하는 항만을 고려하는 표기법, 함수이 상한만 나타낸다.
O(1), O(logN), O(N), O(NlogN), O(N^2), O(N^3), O(2^n)
EX) 시간 제한이 1초인 문제에 대하여

• N의 범위가 500인 경우: 시간 복잡도 O(N^3) 설계
• N의 범위가 2000인 경우: 시간 복잡도 O(N^2) 설계
• N의 범위가 100,000인 경우: 시간 복잡도 O(NlogN) 설계
• N의 범위가 100,000,000인 경우: 시간 복잡도 O(N) 설계

Big-Ω ⇒ 하한 점근
Big-θ ⇒ 그 둘의 평균

(면접 때 질문이었던 표기법 설명하기..)