[C/Python] 시간 복잡도

이번 단원에서는 알고리즘의 실행 횟수를 다항식으로 표현하고, 그 중 가장 영향력이 큰 최고차항의 차수를 찾는 연습을 했습니다.

1. 상수 시간: O(1) (24262번)

입력값 n이 아무리 커져도 실행 횟수가 변하지 않는 가장 이상적인 단계입니다.

• 특징: 반복문 없이 특정 인덱스에 즉시 접근하거나 단순 산술 연산을 수행하는 경우입니다.
• 다항식: f(n) = 1
• 최고차항의 차수: 0 (지수가 없음)

---

2. 선형 시간: O(n) (24263번)

입력값 n에 비례하여 실행 횟수가 늘어나는 단계입니다.

• 특징: n번 반복되는 단일 루프(for, while)가 존재할 때 나타납니다.
• 다항식: f(n) = n
• 최고차항의 차수: 1

---

3. 이차 시간: O(n^2) (24264번, 24265번)

입력값이 10배 늘어나면 실행 시간은 100배(제곱)로 늘어나는 단계입니다.

• 특징: 독립적인 이중 반복문이 중첩되어 있을 때 발생합니다.
• 수학적 분석:
  • 단순 이중 루프: n * n = n^2
  • 조합 형태의 루프: {n(n-1)}{2} = {1}{2}n^2 - {1}{2}n
• 최고차항의 차수: 2
• ⚠️ 주의: n=500,000일 때 n^2은 약 2,500억이므로, C++ 제출 시 반드시 long long 타입을 사용해야 오버플로우를 막을 수 있습니다.

---

4. 삼차 시간: O(n^3) (24266번, 24267번)

루프가 세 번 중첩된 경우로, 데이터가 많아질 때 가장 급격하게 느려집니다.

• 특징: 삼중 반복문 구조에서 나타납니다.
• 수학적 분석:
  • 삼중 루프 조합 ({n}{3}): {n(n-1)(n-2)}{6} = {1}{6}n^3
• 최고차항의 차수: 3

---

5. 점근적 표기법 1 (24313번)

실제 시간 복잡도의 정의인 Big-O 표기법이 수학적으로 성립하는지 판별하는 문제입니다.

• 핵심 조건: f(n) > c * g(n)이 모든 n >= n_0에 대해 만족해야 합니다.
• 체크리스트:
  1. 기울기(a1)가 제한값(c)보다 작거나 같은가? (a1 <= c)
  2. 시작점(n0)에서 실제 값이 상한선보다 아래에 있는가? (f(n0) c n0)

---

🏁 학습 요약 (Self-Feedback)

1. 차수(Degree)의 의미: 다항식에서 가장 큰 지수가 무엇인지 찾는 과정이며, 이는 알고리즘의 성격(상수, 선형, 제곱 등)을 결정합니다.
2. 데이터 타입의 경계: 정보보안 전공자로서 정수 오버플로우(Integer Overflow)를 항상 경계해야 함을 다시금 확인했습니다.
3. 정보처리기사 대비: 2026년 4월 20일 시험에 출제되는 알고리즘 성능 분석의 기초를 완벽히 다졌습니다.