•
input 사이즈에 따라 얼마나 알고리즘의 시간 복잡도가 증가하는가?를 표현하는 방법
•
알고리즘의 크기를 쉽게 파악하는 방법.
•
정확한 디테일이나 시간에 신경쓰지 않고 계산한다.
•
점근적 분석이 필요 → 초기의 차이값을 보는게 아니라 결국에는 어떻게 되는가? 를 집중해서 봐야한다.
시간복잡도를 계산할 때 주의할 점
1.
가장 지배적인 항만 남긴다
•
O(n² + n) → O(n²)
•
O(n + log n) → O(n)
2.
상수는 무시합니다
•
O(2n) → O(n)
•
O(1/2 n²) → O(n²)
