[데이터컴퓨팅] 2회차 수업, 파이썬 기초(2)와 시간복잡도

---

🚀 알고리즘의 성능 분석: 시간 복잡도(Time Complexity) 개념 정리

📚 배경 (Background)

알고리즘과 데이터 구조의 기초를 다루면서,

특히 알고리즘의 효율성 분석을 위한 핵심 도구인
시간 복잡도(Time Complexity) 개념을 중점적으로 배웠다.

평소에는 막연하게 '반복문이 많으면 느리다' 정도로만 이해했었는데,

수업을 통해 보다 자세하게 개념을 이해할 수 있게 되었다.

---

1️⃣ 알고리즘과 복잡도의 정의

✔ 알고리즘(Algorithm)이란?

• 주어진 문제를 해결하기 위한 명확하고 순차적인 절차를 의미한다.
• 요리법(레시피)에 비유할 수 있으며, 알고리즘을 코딩 언어로 구현하는 것이 프로그래밍이다.

✔ 복잡도(Complexity)란?

• 알고리즘이 문제를 해결할 때 사용하는 자원의 양을 나타낸다.
• 보통 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나눈다.

---

2️⃣ 시간 복잡도(Time Complexity) 개념

✔ 정의

• 알고리즘이 입력(input)의 크기(일반적으로 N으로 표현됨)에 따라
  문제를 해결하는 데 걸리는 시간(혹은 실행 횟수)의 증가율을 나타내는 개념이다.
• 정확한 실행 시간이 아니라, 입력의 크기(N)가 증가할 때 실행 횟수의 증가 양상을 보는 것이 핵심이다.

✔ 표기 방법 (Big-O Notation)

• 일반적으로 O( )로 표현한다.
• 상수항과 계수는 무시하고 가장 빠르게 증가하는 항만을 표현한다.
  • 예시: 3N² + 5N + 100 → O(N²)

---

3️⃣ 실행 횟수(Number of Executions)와의 차이점

구분 실행 횟수(Number of Executions) 시간 복잡도(Time Complexity)

개념	실제 코드가 실행된 정확한 횟수	입력의 크기(N)가 증가할 때 실행 횟수의 증가 패턴
표현 방법	정확한 정수 (예: 10, 100, 1000번)	Big-O 표기법 (예: O(N), O(N²), O(logN))
사용 목적	실제 수행 횟수 파악 및 디버깅	알고리즘 성능 분석 및 효율성 비교

---

4️⃣ 자주 등장하는 시간 복잡도의 예

표기 설명 예시 코드

O(1)	상수 시간(Constant Time)	배열의 원소 접근 (arr[0])
O(log N)	로그 시간(Logarithmic Time)	이진 탐색(Binary Search)
O(N)	선형 시간(Linear Time)	단일 반복문(for i in range(N))
O(N²)	제곱 시간(Quadratic Time)	이중 반복문(for i in range(N): for j in range(N))
O(2ⁿ)	지수 시간(Exponential Time)	피보나치 수열 재귀 구현

 

5️⃣ 시간 복잡도별 예시와 분석

---

✅ (1) O(1) - 상수 시간 (Constant Time)

• 입력 크기(N)와 무관하게 항상 동일한 시간이 걸린다.
• 배열에서 특정 요소를 직접 접근하는 경우가 대표적이다.

---

✅ (2) O(log N) - 로그 시간 (Logarithmic Time)

• 입력 크기(N)가 늘어나도 실행 횟수가 느리게 증가 (로그 비율)
• 입력 크기(N)가 2배, 4배, 8배로 늘어나도 실행 횟수는 1, 2, 3씩 아주 조금씩 증가하는 방식으로 매우 효율적이다.

---

✅ (3) O(N) - 선형 시간 (Linear Time)

• 입력 크기(N)와 정확히 비례하여 실행 횟수가 증가한다.
• 입력이 10배 커지면 실행 시간도 정확히 10배가 된다.

---

✅ (4) O(N log N) - 선형 로그 시간 (Linearithmic Time)

• 입력 크기(N)가 늘어남에 따라 N × log N의 속도로 증가한다.
• 대표적으로 병합정렬(Merge Sort), 힙 정렬(Heap Sort)이 이에 해당된다.

---

✅ (5) O(N²) - 제곱 시간 (Quadratic Time)

• 입력 크기(N)의 제곱 비율로 실행 횟수가 증가한다.
• 입력 크기가 10배 늘어나면 실행 시간은 약 100배 늘어난다. 주로 중첩 반복문에서 흔히 나타난다.

---

✅ (6) O(N³) - 세제곱 시간 (Cubic Time)

• 입력 크기(N)의 3제곱 비율로 증가한다.
• 입력 크기가 10배 늘어나면 실행 시간은 약 1000배 늘어난다.

---

✅ (7) O(2ⁿ) - 지수 시간 (Exponential Time)

• 입력 크기(N)가 조금만 커져도 실행 횟수가 기하급수적으로 증가한다.
• 알고리즘 최적화가 반드시 필요한 케이스다. 작은 입력 크기에서도 매우 느리다.

---

🎯 복잡도별 시간 증가율 요약표

• 복잡도입력 크기 N이 10배 증가할 때주요 예시

  O(1)	변화 없음	배열 접근
  O(log N)	매우 느린 증가	이진 탐색
  O(N)	정확히 10배 증가	단일 반복문
  O(N log N)	약 10배보다 조금 더 크게 증가	병합 정렬, 퀵 정렬
  O(N²)	약 100배 증가	이중 반복문
  O(N³)	약 1000배 증가	삼중 반복문
  O(2ⁿ)	기하급수적 증가	재귀 피보나치

• 시간 복잡도는 '성능 평가를 위한 이론적 지표'이며, 실제 성능 테스트와 병행하여
  알고리즘 효율성을 판단하는 중요한 기준이 된다.