12_Algorithms (이산수학)

1. 알고리즘

알고리즘 (Algorithm)
- 어떤 문제를 해결하기 위해 정의된 단계별 절차나 규칙의 집합
- 프로그래밍 언어와 무관하게 추상적으로 존재할 수 있다.

1.1. 알고리즘의 조건

입력 (Input)
- 외부에서 제공되는 0개 이상의 입력이 있어야 한다.
출력 (Output)
- 실행 결과로써 최소한 1개 이상의 출력이 나와야 한다.
명확성 (Definiteness)
- 수행할 각 단계는 모호하지 않고 명확하게 정의되어야 한다.
유한성 (Finiteness)
- 유한한 횟수의 단계를 수행한 후에는 반드시 종료되어야 한다.
수행 가능성 (Effectiveness)
- 모든 명령은 실행 가능해야 한다.

1.2. 알고리즘을 표현하는 방법

알고리즘을 설계하고 타인과 공유할 때 주로 다음과 같은 방식을 사용한다.

자연어 (Natural Language)
- 우리가 일상에서 사용하는 언어로 단계별 절차를 설명한다.
- 읽기 쉽지만 의미가 모호해질 수 있다.
순서도 (Flowchart)
- 알고리즘의 흐름을 약속된 도형과 화살표를 사용하여 시각적으로 표현한다.
- 직관적이지만 복잡한 알고리즘을 표현하는데 한계가 있다.
- 유형: 기본문, 조건문, 순서문, 반복문
의사코드 (Pseudo-code)
- 컴퓨터 프로그래밍 언어와 유사한 형태로, 특정 프로그래밍 언어의 문법을 따르지 않고, 사람이 이해하기 쉽게 핵심만 작성한다.
- Pseudo-code로 작성하는 것이 일반적이다.
프로그래밍 언어
- Python, C, Java 등 실제 컴퓨터가 실행할 수 있는 코드로 직접 작성한다.
- 실행 가능하다.
- 구현의 세부 사항 때문에 알고리즘 핵심 이해를 방해할 수도 있다.

이러한 표현 방법은 명확한 의사소통과 문제 해결 과정 체계화를 위해 필요하다.

2. 알고리즘의 복잡도 분석

Introduction

입력 자료의 개수	프로그램 A: $n^{2}$	프로그램 B: $2^{n}$
n=6	36초	64초
n=100	10000초	$2^{100}$ 초 = $4 \times 1 0^{22}$ 년

어떤 것이 효율적인가?
- 실행 시간이 짧고 (시간 효율성)
- 컴퓨터 자원(메모리)을 적게 쓰는 것 (공간 효율성)

2.1. 시간 복잡도

시간 복잡도 (Time Complexity)
- 입력 크기 $n$ 에 대해 알고리즘이 수행하는 기본 연산 횟수의 증가율을 나타낸 것
- acceptable한 시간 내에 해결이 되는가?

방법은 다음과 같다.

실행 시간 측정
- 실행시간 = 종료 시각 - 현재 시각 (clock() 함수 등 이용)
- 단점
  - 반드시 구현해야 한다.
  - 하드웨어/환경에 따라 달라진다.
  - 성능 평가를 한 데이터에 대해서만 유효하다.
복잡도 분석 (Complexity Analysis)
- 처리시간을 직접 측정하는 대신에,
- 알고리즘의 연산 횟수를 입력 크기 $n$ 에 대한 함수로 표현한다.

대표적인 시간 복잡도는 다음과 같다. (표기법은 다음 절에 설명)

$O (1) < O (lo g n) < O (n) < O (n lo g n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)$

cf. 재귀 함수의 경우 재귀 깊이(Recursion Depth)

2.2. 공간 복잡도

공간 복잡도 (Space Complexity)
- 알고리즘이 실행되는 과정에서 메모리를 얼마나 차지하는지 나타낸다.

2.3. 입력별 분석

보통 최악의 경우를 기준으로 빅오 표기법을 사용한다.

입력별 분석 (Instance-specific Analysis)
- 입력의 구성에 따라 처리시간이 변화한다.
- 같은 알고리즘도 입력의 집합에 따라 다른 실행 시간을 보일 수 있다.

Best Case (최선의 경우)
- 입력에 대한 알고리즘의 수행 시간이 가장 빠른 경우
- 알고리즘 분석에서는 큰 의미가 없다. (참고용)
Worst Case (최악의 경우),
- 입력에 대한 알고리즘의 수행 시간이 가장 느린 경우
- Worst Case를 알고리즘 평가 척도로 주로 사용한다.
  - 상한(upper bound)
  - Average case와 Worst case가 비슷하거나, Worst case가 자주 발생할 수도 있다.
Average Case (평균의 경우)
- 입력에 대한 알고리즘의 수행 시간이 평균적인 경우
- 계산하기가 상당히 어렵다. (현실적인 판단)

2.4. 점근적 표기법

점근적 표기법 (Asymptotic Notation)
- 복잡도 함수를 최고차항만 계수 없이 표기하는 방법
  - 예: $n^{2} + 2 n \to n^{2}$
  - 예: $65536 n + 2000000 \to n$
- 연산이 얼마나 빨리 증가하는가? (증가 속도만을 표현)

표기	의미	역할
O (Big-O)	상한 (upper bound)	최대 성장률
Ω (Big-Omega)	하한 (lower bound)	최소 성장률
Θ (Big-Theta)	정확한 차수 (tight bound)	상한 + 하한
o (little-o)	엄격한 상한	더 느리게 성장
ω (little-omega)	엄격한 하한	더 빠르게 성장

Big-o

$O (g (n)) = {f (n) :$ 모든 $n \geq n_{0}$ 에 대하여 $0 \leq f (n) \leq c g (n)$ 을 만족하는 양의 상수 $c$ 와 $n_{0}$ 가 존재함 $}$

$O (g (n))$ : 증가 속도가 $g (n)$ 과 같거나 낮은 모든 복잡도 함수
최악의 경우(최대 얼마나 느린가)

Big-omega notation

$Ω (g (n)) = {f (n) :$ 모든 $n \geq n_{0}$ 에 대하여 $0 \leq c g (n) \leq f (n)$ 을 만족하는 양의 상수 $c$ 와 $n_{0}$ 가 존재함 $}$

$Ω (g (n))$ : 증가 속도가 $g (n)$ 과 같거나 높은 모든 복잡도 함수
최선의 경우(최소 얼마나 빠른가)

Big-theta notation

$Θ (g (n)) = {f (n) :$ 모든 $n \geq n_{0}$ 에 대하여 $0 \leq c_{1} g (n) \leq f (n) \leq c_{2} g (n)$ 을 만족하는 양의 상수 $c_{1}, c_{2}$ 및 $n_{0}$ 가 존재함 $}$

$θ (g (n))$ ): 증가 속도가 $g (n)$ 과 같은 모든 복잡도 함수
정확한 성장 속도

Little-o notation

$o (g (n)) = {f (n) :$ 임의의 양의 상수 $c > 0$ 에 대하여, 모든 $n \geq n_{0}$ 에 대해 $0 \leq f (n) \leq c g (n)$ 을 만족하는 상수 $n_{0} > 0$ 가 존재함 $}$

Little-omega notation

$ω (g (n)) = {f (n) :$ 임의의 양의 상수 $c > 0$ 에 대하여, 모든 $n \geq n_{0}$ 에 대해 $0 \leq c g (n) \leq f (n)$ 을 만족하는 상수 $n_{0} > 0$ 가 존재함 $}$

복잡도 분석 예시

4. 알고리즘의 복잡도 분석 예시

3. 프로시저

프로시저 (Procedure)
- 특정 작업을 수행하기 위해 프로그래밍 언어로 작성된 일련의 명령어들의 집합
- 함수(Function), 서브루틴(Subroutine), 메서드(Method) 등과 유사한 개념으로, 코드의 재사용성을 높이기 위해 사용된다.

3.1. 프로시저의 특징

구현 중심
- 알고리즘과 달리 실제 컴퓨터가 실행할 수 있는 특정 프로그래밍 언어로 작성된 구체적인 코드 블록이다.
종료 여부
- 프로시저는 반드시 종료될 필요는 없다.
- 예를 들어, 운영체제의 데몬이나 무한히 대기하는 이벤트 루프처럼 특정 목적을 위해 무한히 실행되는 프로시저도 존재할 수 있다.
컴퓨터 환경 의존적
- 실행되는 하드웨어나 소프트웨어 환경의 제약을 받을 수 있다.

Archive

탐색기