알고리즘 소개

1. 알고리즘 분석

정확성 분석 

• 유효한 입력에 대해 일정 시간내에 정확한 결과의 생성 여부 

효율성 분석 

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정/평가
• 공간 복잡도 (space complexity): 메모리의 양 = 정적 공간 + 동적 공간
• 시간 복잡도: 수행시간 = 알고리즘의 실행에서부터 완료까지 걸리는 시간 

시간 복잡도

알고리즘 수행시간 = Σ{각 연산이 수행되는 횟수}

수행 시간에 영향을 미치는 요인 

입력크기 (리스트 원소의 개수, 행렬의 크기 등)

• 입력크기 n이 커질수록 수행시간 증가 > 입력크기 n의 함수 f(n)으로 표현 

입력 데이터의 상태 

S(n) : 크기 n인 입력들의 집합 
P(i) : 입력 i가 발생할 확률
T(i) : 입력 i 에 대한 알고리즘의 수행시간

• 평균 수행시간 
$$ A(n) = \sum_{i=1}^{n} P(i) \cdot T(i) $$
• 최선 수행시간

$$ B(n) = \min_{i \in S(n)} T(i) $$

• 최악 수행시간 -> "아무리 오래 걸려도 이 시간안에는 수행된다" 알고리즘 간 우열을 가리기 좋음

$$ W(n) = \max_{i \in S(n)} T(i) $$

2. 점근 성능

점근성능이란

• 입력 크기 n이 무한히 커짐에 따라 결정되는 성능 
• 수행시간의 정확한 값이 아닌 어림값으로 수행시간의 증가 추세 파악이 쉬움 
• 수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현 

점근성능의 표기법 

빅오(Big-O)

• 최악 수행 시간의 상한을 나타냄.
• 입력 크기 n이 증가할 때, 수행 시간이 "최대" 얼마나 걸릴 수 있는지를 분석.
• 어떤 입력에서도 이보다 느리진 않다는 보장을 함.
• 최대 f(n)만큼 시간이 걸린다 

빅오메가(Big-Ω)

• 최선(Best-case) 수행 시간의 하한을 나타냄.
• 어떤 입력에서 최소한 이만큼의 시간이 걸린다.
• 최소 f(n)의 시간이 걸린다

빅쎄타(Big-Θ)

• 시간 복잡도의 상한과 하한이 일치하는 경우.
• 수행 시간이 항상 f(n)과 비슷하게 걸린다는 의미.
• 최악과 최선이 f(n)으로 수렴한다 

시간 복잡도 순서 

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)

표기법	이름	예시	특징
O(1)	상수 시간	해시 테이블 조회, 배열 인덱싱	입력 크기와 관계없이 항상 일정한 시간
O(log n)	로그 시간	이진 탐색	입력 크기가 커져도 상대적으로 증가 속도가 느림
O(n)	선형 시간	단순 반복문 (배열 순회)	입력 크기에 비례하여 실행 시간 증가
O(n log n)	선형로그 시간	퀵 정렬, 병합 정렬	거의 모든 효율적인 정렬 알고리즘
O(n²)	이차 시간	버블 정렬, 선택 정렬, 삽입 정렬	중첩된 반복문 (이중 for문)
O(2ⁿ)	지수 시간	피보나치 (재귀), 부분집합 생성	입력 크기가 조금만 커져도 매우 느려짐
O(n!)	팩토리얼 시간	외판원 문제(완전 탐색)	가장 비효율적, 거의 사용 불가능

빅오 함수에 따른 연산 시간의 증가추세 

n	logn	nlogn	n²	n³	2ⁿ
1	0	0	1	1	2
2	1	2	4	8	4
4	2	8	16	64	16
8	3	24	64	512	256
16	4	64	256	4096	65536
32	5	160	1024	32768	4294967296

3. 순환 알고리즘 (재귀)

• 알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 호출하여 수행하는 형태의 알고리즘
• 재귀적인 알고리즘에서는 현재 문제를 더 작은 문제로 나누어 해결하는데 이 과정에서 수행시간을 점화식으로 표현할 수 있음

점화식 

• 이전 단계의 값을 이용해 다음 값을 계산하는 형태의 수식 
• 예를 들어 이진탐색은 문제를 절반으로 줄여서 풀기 때문에 수행시간은 다음과 같음 

$$ T(n) = T(n/2) + O(1) $$ 

• T(n/2) : 문제를 반으로 줄여서 해결할때의 수행 시간
• O(1) : 현재 단계에서 수행하는 추가 작업의 시간 
• 즉 현재 크기 n의 문제를 크기 n/2로 줄이고 그 과정에서 추가적인 일정한 작업(이진 탐색에서는 가운데 원소 비교와 방향 결정 과정)을 수행

점화식의 폐쇄형 

• 위와 같은 점화식은 재귀적인 형태라 실제 계산이 어려움. 이를 일반적인 수식으로 변환한 것이 폐쇄형 표현
• 반복적인 관계를 없애고 한번에 계산할 수 있도록 만든 것 

위의 이진 탐색의 점화식을 폐쇄형으로 풀면 

1. 첫번째 호출:

$$ 
T(n) = T(n/2) + O(1) 
$$

2. 두번째 호출:

$$ 
T(n/2) = T(n/4) + O(1) 
$$ 

$$ 
T(n) = (T(n/4) + O(1)) + O(1) = T(n/4) + 2O(1) 
$$ 

3. 세번째 호출:

$$ 
T(n/4) = T(n/8) + O(1) 
$$

$$ 
T(n) =  (T(n/8) + O(1)) + 2O(1) = T(n/8) + 3O(1) 
$$ 

이렇게 반복하다 보면 

$$ 
T(n) = T(n/2^k) + kO(1)
$$

점화식은 입력 크기가 1이 될 때 끝나므로,

$$ 
n/2^k = 1
$$

이 되는 k를 찾으면  

$$ 
n = 2^k 
$$

양변에 로그를 취하면,

$$ 
k = \log_2 n 
$$ 

처음 점화식에서 \( T(1) \) 은 \( O(1) \) 이 되고, k는 \( \log_2 n \) 이 되므로 

$$ 
T(n) = O(1) + O(\log n) = O(\log n) 
$$

따라서 최종적으로 

$$ 
T(n) = O(\log n) 
$$

이렇게 식이 나오게 된다. 

실제 알고리즘들의 점화식과 폐쇄형 정리

알고리즘	점화식	폐쇄형
이진 탐색	T(n) = T(n/2) + O(1)	O(log n)
퀵 정렬 (최악)	T(n) = T(n-1) + O(n)	O(n²)
퀵 정렬 (최선, 평균)	T(n) = 2T(n/2) + O(n)	O(n log n)
병합 정렬	T(n) = 2T(n/2) + O(n)	O(n log n)