Chap 1.3 Analysis of Algorithms

왜 알고리즘을 분석해야 할까?

• 같은 문제를 푸는 여러 알고리즘이 있을 수 있음
• 어떤 게 더 빠르고 효율적인지를 판단하려면 분석 필요
• 실제 컴퓨터 성능, 언어, 구현 방법에 따라 실행 시간은 달라지지만
  이론적 분석은 입력 크기 n에 따른 경향성을 알려줌

---

📄 원문

In general, a time complexity analysis of an algorithm is the determination of how
many times the basic operation is done for each value of the input size.

---

✅ 해석

일반적으로, 알고리즘의 시간 복잡도 분석이란
입력 크기의 각 값에 대해 기본 연산이 몇 번 수행되는지를 구하는 것이다.

---

분석의 기본 구성 요소

구성요소	의미
입력 크기(input size)	문제의 크기를 나타냄 (ex: 배열의 길이 n)
기본 연산(basic operation)	분석 대상이 되는 반복 연산 (ex: 비교, 덧셈 등)
T(n)	입력 크기가 n일 때 기본 연산의 실행 횟수

---

입력 크기 예시

• 배열의 합 계산: 입력 크기 = 원소 개수 n
• 행렬 곱셈: 입력 크기 = 행렬 크기 n × n → 그냥 n으로 사용
• 피보나치 수 계산: 입력은 n, 하지만 입력 크기는 log₂n이 될 수도 있음 (정수의 비트 수)

---

시간복잡도 종류

표기	의미
T(n)	모든 입력에 대해 항상 같은 연산 횟수 → “every-case”
W(n)	가장 많은 연산 → “최악(worst-case)”
A(n)	평균적인 연산 → “평균(average-case)”
B(n)	가장 적은 연산 → “최선(best-case)”

---

🔍 예시 분석들

---

🔹 [예제] Algorithm 1.2 – Add Array Members

sum ← 0  
for i = 1 to n  
  sum ← sum + S[i]

 

• 입력 크기: n
• 기본 연산: 덧셈 1번
• 반복 횟수: n번
• T(n) = n

---

🔹 [예제] Algorithm 1.3 – Exchange Sort

for i = 1 to n-1  
  for j = i+1 to n  
    if S[j] < S[i] then exchange

 

 

• 비교 횟수 총합:(n−1)+(n−2)+...+1=n(n−1)2(n−1)+(n−2)+...+1= n(n−1)​ / 2
• T(n) = O(n²)

---

🔹 [예제] Algorithm 1.1 – Sequential Search

• x가 맨 앞에 있으면 1번, 없으면 n번 → 입력에 따라 달라짐
• 따라서 T(n) 없음, 대신:

분석	결과
W(n)	n (x가 마지막 or 없음)
B(n)	1 (x가 첫 번째 원소)
A(n)

⚠️ 평균 분석 시 주의

• 평균 = 대표값이 아니다
  예: 응급 시스템처럼 단 한 번의 오래 걸리는 경우도 위험
• 그래서 실전에서는 평균보다 최악 분석(W(n))이 더 중요!!

키워드 정리

용어	뜻
T(n)	모든 입력에서 항상 같은 연산 횟수
W(n)	최악의 경우 연산 횟수
A(n)	입력의 분포를 고려한 평균 연산 횟수
B(n)	최선의 경우 연산 횟수
기본 연산	비교, 덧셈 등 반복되는 연산 (분석 대상)
입력 크기	문제를 정의하는 데이터의 양 (ex: 배열 크기)