알고리즘 성능 평가(빅오 표기법)

1. 복잡도(Complexity)

📝 알고리즘의 복잡도는 알고리즘이 실행되는 동안 소요되는 자원의 양 또는 알고리즘의 성능을 수학적으로 나타낸 것이다. 일반적으로 시간 복잡도와 공간 복잡도로 나뉘어진다.

• 시간 복잡도(Time Complexity): 입력 크기에 따라 소요되는 시간의 증가 정도를 나타낸다.
• 공간 복잡도(Space Complexity): 실행 중에 필요로 하는 메모리 공간의 양을 나타낸다.

---

2. 빅오 표기법(Big-O Notation)

• 알고리즘의 성능을 나타내고 비교하기 위한 표기 방법 중 하나로, 시간 복잡도와 공간 복잡도 예측 시 사용된다.
• 📌 가장 빠르게 증가하는 항만을 고려하는 표기법이다.
  • ex) $10x^2+5x+10,000$ => $O(N^2)$

---

3. 빅오 표기법(시간 복잡도)

순위	명칭	특징	예시
$O(1)$	상수 시간	입력 크기에 상관없이 항상 같은 시간이 소요됨.	수학적 계산, Hash 테이블, 배열의 특정 인덱스 접근
$O(logN)$	로그 시간	$O(1)$ 다음으로 빠른 시간 복잡도	이진 탐색, 이진 트리, 분할 정복
$O(N)$	선형 시간	입력 크기가 증가함에 따라 시간이 같은 비율로 증가함.	일반적인 반복문, 배열 순회
$O(NlogN)$	로그 선형 시간	분할 정복 방식, 주요 정렬 알고리즘	퀵 정렬, 병합 정렬, 힙 정렬
$O(N^2)$	이차 시간	입력 크기 증가 시 n의 제곱 비율로 증가함.	2차원 배열 순회
$O(N^3)$	삼차 시간	입력 크기 증가 시 n의 세제곱 비율로 증가함.	행렬 곱셈, 플로이드 워셜
$O(2^n)$	지수 시간	가장 느린 시간 복잡도	완전 탐색

---

✨ 4. 알고리즘 설계 팁

알고리즘 문제 풀이 시 가장 먼저 확인해야 할 것은 🕐시간제한이다.
일반적으로 아래 표와 같은 기준으로 알고리즘을 설계하면 문제를 풀 수 있다.

범위	시간 복잡도
$N<=500$	$O(N^3)$
$N<=2000$	$O(N^2)$
$N<=100,000$	$O(NlogN)$
$N<=10,000,000$	$O(N)$

지문 읽기 ➡️ 요구사항(복잡도) 분석 ➡️ 아이디어 탐색