Chap1 1.2 The Importance of Developing Efficient Algorithms

왜 효율성이 중요한가?

❓ "컴퓨터 성능이 계속 좋아지는데 굳이 알고리즘 효율성을 따져야 해?"
→ Yes. 무조건 중요함.

• 컴퓨터가 빨라져도, 문제 크기(input size) 는 더 빠르게 커짐
• 좋은 알고리즘은 수십 배, 수백 배 빠른 성능 차이를 만듦

---

🔍 두 알고리즘 비교 사례

---

🔹 1.2.1 Sequential Search vs Binary Search

🧪 문제: 정렬된 배열에서 x가 있는지 찾기

알고리즘	방식	비교 횟수(최악의 경우)
Sequential Search	처음부터 끝까지 순서대로 비교	n회
Binary Search	중간값 기준으로 절반씩 줄여감	log₂n + 1회

📌 핵심 비교

• n = 4,294,967,296일 경우:
  • Sequential: 약 43억 번 비교
  • Binary: 단 33번만 비교

아무리 컴퓨터가 빨라도 Sequential은 수 초, Binary는 거의 즉시 결과!

문제 상황

목표: 정렬된 배열 S[1..n] 안에서 원소 x를 찾기
→ x의 위치(index)를 반환하거나, 없으면 0

🔴 Sequential Search (선형 탐색)

procedure SequentialSearch(S[1..n], x)
  for i = 1 to n
    if S[i] == x then return i
  return 0

특징:

• 앞에서부터 하나씩 순차적으로 비교
• 배열이 정렬되어 있지 않아도 가능
• 최악의 경우: 끝까지 비교 → n번

시간복잡도:

• 최선: O(1)
• 평균: O(n/2)
• 최악: O(n)

---

✅ Binary Search (이진 탐색)

🔁 기본 개념

1. 중간 값(mid)을 선택해서 x와 비교
2. 같으면 찾은 것 → 반환
3. x가 더 작으면 → 왼쪽 절반만 탐색
4. x가 더 크면 → 오른쪽 절반만 탐색
5. 반복

---

📦 사용 변수

 

변수	의미
low	현재 탐색 범위의 시작 인덱스
high	현재 탐색 범위의 끝 인덱스
mid	중간 위치 인덱스 ((low + high) // 2)

procedure BinarySearch(S[1..n], x)
  low ← 1
  high ← n
  while low ≤ high
    mid ← ⌊(low + high)/2⌋
    if S[mid] == x then return mid
    else if x < S[mid] then high ← mid - 1
    else low ← mid + 1
  return 0

특징:

• 정렬된 배열에서만 사용 가능
• 매 단계마다 탐색 범위를 절반으로 줄임
• 매우 빠름! (로그 시간)

시간복잡도:

• 항상 O(log₂n) (약간의 상수 차이로 +1 포함)

❗ 시험 대비 체크 포인트

질문	답변 요약
Binary Search의 전제 조건은?	배열이 정렬되어 있어야 함
왜 log₂n만큼 빠른가?	매번 범위를 절반씩 줄이기 때문
Binary Search 시간복잡도는?	O(log n)
Sequential Search와의 차이는?	Binary는 훨씬 더 적은 비교 횟수로 탐색 가능

---

🔹 1.2.2 피보나치 수열 알고리즘 비교

📍 문제: n번째 피보나치 수를 구하라

---

🚨 비효율적: Algorithm 1.6 (재귀 recursive)

function fib(n)
  if n == 0 or n == 1 then
    return n
  return fib(n-1) + fib(n-2)

• 같은 값을 여러 번 반복 계산
• 계산량이 2^(n/2) 이상 → 지수적 증가
• 예: n=120이면 수십 년 이상 걸릴 수도 있음 (!)

---

효율적: Algorithm 1.7 (반복 Iterative)

function fib2(n)
  f[0] ← 0
  f[1] ← 1
  for i = 2 to n
    f[i] ← f[i-1] + f[i-2]
  return f[n]

• 모든 항을 한 번만 계산 → O(n) 시간
• n=120도 순식간에 계산

---

💡 결론: 알고리즘 선택이 생명이다!

알고리즘	시간복잡도	실행 시간
재귀 피보나치	O(2^n)	수십 년
반복 피보나치	O(n)	0.0000001초 수준

---

🎯 핵심 키워드 요약

• 효율성은 문제 크기가 커질수록 필수
• 비효율 알고리즘은 아무리 좋은 컴퓨터도 소용 없음
• 이론적 분석은 실제 성능에 큰 영향을 줌
• 좋은 설계 = 수천 배 이상의 실행 시간 절약

---

📌 시험 대비 체크 포인트

질문	답변 요약
왜 효율적인 알고리즘이 중요한가?	문제 크기가 커지면, 비효율적인 알고리즘은 현실적으로 사용 불가
Binary Search가 빠른 이유는?	매번 검색 범위를 절반으로 줄이기 때문
재귀 피보나치가 느린 이유는?	중복 계산이 너무 많아서 계산량이 지수적으로 증가
효율적인 피보나치 계산법은?	반복문으로 계산 + 이전 두 항만 기억 → O(n)

---

[참고사항]

🧮 피보나치 수열 (Fibonacci Sequence)

---

정의

피보나치 수열은 다음과 같은 점화식(재귀식)으로 정의된다:

F(0)=0,F(1)=1F(n)=F(n−1)+F(n−2),n≥2

즉, 이전 두 항을 더해서 다음 항을 만드는 수열이다.

▶️ 처음 몇 개 항은?

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...