✍️Today I Learned

1. Big-O 표기법

---

Big-O 표기법

알고리즘의 성능은 연산 횟수로 평가한다.
연산의 종류

1. 반복문의 수행 횟수
2. 비교 / 대입 / 산술 연산자 사용 횟수
3. 조건에 따른 연산 횟수

점근적 표기법
: 연산 횟수의 추이 파악. 연산 횟수에 가장 많은 영향을 주는 부분을 기준으로 변화 양상을 분석하는 게 핵심이다.
👉 Big-O 표기법

최악의 경우를 기준으로 점근적 표기법을 활용하여 성능을 표기한다. -> 점근적 상한

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2ⁿ)	20~25
O(N³)	200~300
O(N²)	3,000~5,000
O(Nlog N)	100만
O(N)	1,000~2,000만
O(log N)	10억

O(log N): 범위를 반복해서 절반으로 줄여 나가는 경우

N을 1이 될때까지 1/2씩 줄여나간 횟수가 k일때
N(1/2)^k = 1 
1/(2^k) = 1/N
2^k = N
k = log N // 2는 N이 아주 큰 수 일때 무시해도 됨

🤔Vector의 메모리 재할당

벡터 끝에 요소를 추가하다가 현재 용량을 초과하는 경우 메모리를 재할당하게 되는데 이때 시간 복잡도는 O(N)이다.
push_back()의 시간 복잡도: O(1)
재할당 시 이전 메모리를 해제하고 새 메모리에 복사: O(N)

📌재할당을 피하려면 reserve()로 미리 용량 확보 가능

예상 요소 수	reserve() 필요 여부	이유
0 ~ 20	거의 의미 없음	재할당 비용 무시 가능
100 이상	사용 권장	재할당 횟수가 꽤 늘어남
1,000 이상	적극 권장	매번 복사 비용 무거움
10,000 이상	반드시 사용	재할당 없이 할당하는 게 훨씬 빠름