성능 분석

1. 🔍 성능 분석이란?

문제를 해결하는 여러 알고리즘 중 가장 효율적이고 최적화된 방법을 선택하기 위한 분석

---

2. 📌 알고리즘 분석 기준

기준	설명
정확성	올바른 입력에 대해 정해진 시간 내에 정확한 출력을 생성하는가
명확성	이해하기 쉽고, 명확하게 작성되어 있는가
수행량	알고리즘의 핵심 연산량을 기반으로 분석
최적성	시스템 환경에 따라 메모리, 수행 시간 등 자원이 최적화되어 있는가

---

3. 🧠 알고리즘 분석 방법

📦 공간 복잡도 (Space Complexity)

• 고정 공간: 프로그램 크기나 입력 크기와 무관 (ex. 변수, 상수)
• 가변 공간: 입력 크기나 실행 과정에 따라 변화
  (ex. 배열, 스택, 재귀 호출 정보 등)

공식:
공간 복잡도 = 고정 공간 + 가변 공간

---

⏱ 시간 복잡도 (Time Complexity)

• 컴파일 시간 + 실행 시간
• 반복문/재귀 등 실행 빈도를 기반으로 실행 시간을 계산
• 주로 실행 시간을 분석

---

4. 📐 시간 복잡도 예시: 피보나치 수열

피보나치 수열:
f(0) = 0, f(1) = 1,
f(n) = f(n-1) + f(n-2) (단, n ≥ 2)

• 해당 알고리즘의 실행 시간 함수: 4n + 2
• 가장 큰 영향력을 미치는 항 4n → 계수 생략 → O(n)으로 표기

빅-오(Big-O) 표기법:
입력 크기 n이 커짐에 따라 증가하는 연산 횟수의 상한을 표현

⌛ 대표적인 시간 복잡도

표기	설명
O(1)	상수 시간
O(log n)	로그 시간
O(n)	선형 시간
O(n log n)	로그-선형 시간
O(n²)	이중 반복문 등
O(2ⁿ)	지수 시간 (비효율)

---

🖼 참고 이미지

피보나치 수열 실행 흐름도

실행 빈도수 분석 표1

실행 빈도수 분석 표2

표2