[알고리즘] 2. Complexity of Algorithm

1. Algorithms

알고리즘이란?

알고리즘은 컴퓨터 프로그램을 구성하는 개별 모듈들을 설계하는 것이며, 각 모듈은 정렬 같은 특정 작업을 수행한다.

이러한 작업들은 우리가 해결하고자 하는 문제(problem)이고, 문제는 본질적으로 우리가 답을 찾고자 하는 질문이다. 

알고리즘은 단순한 아이디어가 아니라 문제를 해결하기 위한 단계적 절차이다.

이 절차는 신중하게 설계되어야 하며, 입력을 받아 출력(해결책)으로 변환한다.

 

문제는 특정 값이 정해지지 않은 parameter(매개변수)를 포함하고 있다.

이 parameter에 값을 넣으면 하나의 문제 instance가 된다.

즉, 하나의 문제는 다양한 instance의 집합이라 볼 수 있다.

 

2. 알고리즘 표현 방법

• C와 같은 구현 언어
• pseudocode
• 영어 서술

중요한 것은 어떤 언어를 쓰느냐보다 그 알고리즘이 얼마나 명확하고 이해하기 쉬운가이다. 

좋은 알고리즘은 아래 2가지 속성을 갖추어야 한다.

• 정확성(correctness): 유효한 입력에 대해 항상 올바를 출력을 제공해야 한다.
• 효율성(efficiency): 입력을 처리하는 데 시간이 너무 오래 걸리지 않아야 한다.

2-1. 정확성 예시

Traveling Salesperson Problem (TSP)

: N개의 도시와 각 도시 간의 거리가 주어졌을 때, 모든 도시를 한 번씩 방문하고 시작 도시로 돌아오는 최단 경로를 찾는 문제.

• Nearest Neighbor: 가장 가까운 도시를 계속 방문
• 완전 탐색 방법: 가능한 모든 경로를 탐색해 가장 짧은 경로를 선택

2-2. 효율성 예시

Odd Number Problem

: n이 홀수인지 판별하기 위해, 

• 1부터 n까지 세며 홀짝을 번갈아 말하는 방법 X
• 소인수분해해서 2가 있는지 확인 X
• 미리 만든 테이블을 조회 X
• 가장 효율적인 방법은 마지막 비트(짝수=0, 홀수=1)를 확인하는 것 O

 

3. 탐색 알고리즘 비교 : 선형 탐색 vs 이진 탐색

어떤 값 x가 배열에 있는지 확인하는 문제를 생각해보자.

• 선형 탐색 (Sequential Search)
  • 배열의 앞에서부터 하나씩 비교 → 최악은 배열크기 n만큼 모두 비교, x가 있다면 최대 n 없다면 정확히 n번 비교
• 이진 탐색 (Binary Search)
  • 전제조건: 배열이 정렬되어 있어야 한다. 
  • 탐색 범위를 매번 절반으로 줄여가며 비교 → 비교 횟수 log₂(n) 으로 훨씬 효율적인 탐색 방법

 

4. 알고리즘 분석 (Analysis of Algorithms)

알고리즘이 효율적인지 판단하려면 분석이 필요하다.

분석의 핵심은 입력 크기 n이 커질수록 실행 시간이나 메모리 사용량이 어떻게 변하는가?

 

보통 가장 중요한 자원은 실행시간(time)이지만 메모리 사용량(space)도 고려할 수 있다.

 

분석을 실행 없이도 수행할 수 있어야 하며, 알고리즘 자체만 보고 평가할 수 있어야 한다. 

 

4.1 알고리즘 복잡도

복잡도 분석이란 기본 연산이 입력 크기 n에 따라 몇 번 수행되는가.

이때 입력 크기 n을 기준으로 복잡도를 함수 T(n)으로 표현.

알고르즘은 입력의 크기에 따라 성능이 달라지기 때문에, 복잡도는 컴퓨터나 언어와 무관하게, 오직 연산 횟수 관점에서 측정한다.

 

입력 크기별 분석

• Worst Case (최악) : 가장 많은 연산이 필요한 경우 → 가장 자주 사용
• Best Case (최선): 가장 적은 연산으로 끝나는 경우
• Average Case (평균): 보통의 경우 → 수학적으로 분석이 어렵다.

대부분의 알고리즘 분석에서는 Worst Case를 기준으로 복잡도를 판단한다.

 

5. 점근적 분석 (Asymptotic Analysis)

점근석 분석이 필요한 이유

알고리즘의 실행 시간을 정확히 계산하려 하면 너무 복잡할 수 있다. 대략적인 성장 추세만 보는게 중요하다.

 

점근적 분석의 기본 원칙

• 상수 계수는 무시한다.
• 가장 빠르게 증가하는 항만 남긴다.

 

6. Big-O 표기법

O(g(n)) = f(n)이 어떤 일정 이후로 c*g(n)보다 작거나 같은 함수들의 집합.

f(n) ≤ c × g(n)이 n ≥ n₀인 지접부터 항상 참이면, f(n)은 O(g(n))이다.

★주의: Big-는 집합이다. 따라서 n = O(n²)은 잘못된 표현이다.→ f(n) ∈ O(g(n)) 이 처럼 표현해야 한다.

 

실제 알고리즘 예시

- 버블 정렬 Bubble Sort

for i = 1 to n
   for j = n down to i+1
      if A[j] < A[j-1]
         swap A[j], A[j-1]

-> 비교횟수 = n²/2

-> 교환횟수 = n²/2

--> Θ(n²)

 

- 삽입 정렬 Insertion Sort

for j = 2 to n
   key = A[j]
   while i > 0 and A[i] > key
      A[i+1] = A[i]
      i = i - 1
   A[i+1] = key

-> 최악: Θ(n²)

-> 최선: Θ(n)

 

7. 수학적 귀납법

: 어떤 명제가 모든 자연수에 대해 참임을 보이는 방법

 - 기저 단계 (Basis Step): n=1일 때 참임으로 확인

 - 귀납 단계 (Inductive Step): n일 때 참이라 가정하고, n+1일 때도 참임을 증명

 

8. 전체 요약

- 알고리즘은 문제 해결을 위한 절차로, 정확성과 효율성을 갖춰야 한다.

- 알고리즘 분석은 시간과 공간의 사용량을 정량적으로 측정하고 비교하는 과정이다.

- 입력 크기 n에 따른 연산 횟수를 T(n)으로 표현하고, 점근적 표기법 O, Ω, Θ를 통해 성능을 분석한다.

- 실제 정렬 알고리즘 (버블/삽입)의 시간 복잡도도 이를 통해 계산하며, 수학적 도구를 이용해 증명할 수 있다.